text: Binary Insertion Sort | iterative implementation ; Function to sort an array a [ ] of size ' n ' ; find location where selected should be inseretd ; Move all elements after location to create space ; Driver Code
code: using System ; class GFG { static int binarySearch ( int [ ] a , int item , int low , int high ) { while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( item == a [ mid ] ) return mid + 1 ; else if ( item > a [ mid ] ) low = mid + 1 ; else high = mid - 1 ; } return low ; } static void insertionSort ( int [ ] a , int n ) { int i , loc , j , selected ; for ( i = 1 ; i < n ; ++ i ) { j = i - 1 ; selected = a [ i ] ; loc = binarySearch ( a , selected , 0 , j ) ; while ( j >= loc ) { a [ j + 1 ] = a [ j ] ; j -- ; } a [ j + 1 ] = selected ; } } public static void Main ( String [ ] args ) { int [ ] a = { 37 , 23 , 0 , 17 , 12 , 72 , 31 , 46 , 100 , 88 , 54 } ; int n = a . Length , i ; insertionSort ( a , n ) ; Console . WriteLine ( " Sorted ▁ array : " ) ; for ( i = 0 ; i < n ; i ++ ) Console . Write ( a [ i ] + " ▁ " ) ; } }