Program for Binary Insertion Sort using Python

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

Program for Binary Insertion Sort

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.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.