Introduction

Binary insertion sort is the extended version of insertion sort algorithm that uses binary search algorithm to append the element at the right location. We can reduce the time complexity to O(log i) from O(i) ( normal insertion sort time complexity)  in worst case. In this article we will explore Program for Binary Insertion Sort using Python.

Program for Binary Insertion Sort using Python

def b_search(arr, ele, first, last):
    if first == last:
        if arr[first] > ele:
            return first
        else:
            return first+1
    if first > last:
        return first
    mid = (first + last)/2
    mid = int(mid)
    if arr[mid] < ele:
        return b_search(arr, ele, mid+1, last)
    elif arr[mid] > ele:
        return b_search(arr, ele, first, mid-1)
    else:
        return mid
         
def sort(arr):
    for idx in range(1, len(arr)):
        ele = arr[idx]
        j = b_search(arr, ele, 0, idx-1)
        arr = arr[:j]+ [ele] + arr[j:idx] + arr[idx+1:]
    return arr
       
ip_arr = [87, 8, 14, 0]
print("The sorted array is: ",sort(ip_arr))

Output

Explanation

Input array = [ 7, 12, 81, 52 ]

The steps followed for binary insertion sort are:

1. Insert the elements of index 0 and 1 into subarray that has length 1 from 0 position.
2. Using binary search, find the position (pos) and shift the position of elements by 1 to right side.
3. Update the element at index = pos by the element value at index = i.
4. Now insert the element at index 2 and repeat step 2 – 3.
5. Repeat the above steps for the other elements in the array.
6. Return the sorted array.