Select Page

# Program for Binary Insertion Sort using Python

by | Apr 23, 2021 | Python Programs

Home » Python » Python Programs » 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 ## 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.

## Author

• A Full Stack Developer with 10+ years of experience in technical content creation.

• 