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
def binarySearch ( a , item , low , high ) : NEW_LINE INDENT while ( low <= high ) : NEW_LINE INDENT mid = low + ( high - low ) // 2 NEW_LINE if ( item == a [ mid ] ) : NEW_LINE INDENT return mid + 1 NEW_LINE DEDENT elif ( item > a [ mid ] ) : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT high = mid - 1 NEW_LINE DEDENT DEDENT return low NEW_LINE DEDENT ' NEW_LINE def insertionSort ( a , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT j = i - 1 NEW_LINE selected = a [ i ] NEW_LINE loc = binarySearch ( a , selected , 0 , j ) NEW_LINE while ( j >= loc ) : NEW_LINE INDENT a [ j + 1 ] = a [ j ] NEW_LINE j -= 1 NEW_LINE DEDENT a [ j + 1 ] = selected NEW_LINE DEDENT DEDENT a = [ 37 , 23 , 0 , 17 , 12 , 72 , 31 , 46 , 100 , 88 , 54 ] NEW_LINE n = len ( a ) NEW_LINE insertionSort ( a , n ) NEW_LINE print ( " Sorted ▁ array : ▁ " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( a [ i ] , end = " ▁ " ) NEW_LINE DEDENT