Python Program for Binary Insertion Sort

Binary Insertion Sort is a more efficient variant of Insertion Sort. In this tutorial, we will sort an array with help of binary insertion sort.

Binary Insertion Sort - Basic Introduction

In binary insertion sort, binary search is used to identify the correct position to insert the selected item. It basically reduces the number of comparisons from the normal insertion sort method. We must identify the right location of the element being considered in Insertion Sort. The number of comparisons would be reduced if we utilized Binary Search for this search function. As a result, Binary Insertion Sort employs binary search during each iteration to identify the correct position to insert the selected item.

Algorithm

As of now, we have a rough understanding of how radix sort is performed. For better understanding, let's dive deep into the algorithm followed by the code:

1. Create a binary_insertionSort function that accepts a list as an input.
2. Create a loop with the loop variable i counting from 1 to the length of the list – 1 within the function.
3. Set the temp to the value of the element at index i
4. Call binary_search
5. Set pos++ the above call's return value
6. From indexes pos + 1 to i shift all items one place
7. set alist[pos] to temp
8. To find a key in a list between indexes start and end – 1 inclusive – a function uses binary search.
9. If the key cannot be found, the index of the smallest element smaller than the key is returned.
10. If the key is smaller than the first element, it returns -1
11. The array is now sorted
12. Print the array

Program for Binary Insertion Sort

The source code for a Python program that implements binary insertion sort is given below. The output of the program is displayed below. In this program, the user is asked to enter the list and after that, the sorted form of the list is prompted by the compiler:

def binary_insertionsort(array):
    for i in range(1, len(array)):
        temp = array[i]
        pos = binary_search(array, temp, 0, i) + 1
 
        for k in range(i, pos, -1):
            array[k] = array[k - 1]
 
        array[pos] = temp

def binary_search(array, key, strt, end):
    if end - strt <= 1:
        if key < array[strt]:
            return strt - 1
        else:
            return strt
 
    middle = (strt + end)//2
    if array[middle] < key:
        return binary_search(array, key, middle, end)
    elif array[middle] > key:
        return binary_search(array, key, strt, middle)
    else:
        return middle
 
 #driver code
array = input('Enter the array numbers: ').split()
array = [int(a) for a in array]
binary_insertionsort(array)
print('The Sorted array is: ', end='')
print(array)

Enter the array numbers: 5 4 3 98 76 97
The Sorted array is: [3, 4, 5, 76, 97, 98]

Conclusion

In this tutorial, we have performed the Binary Insertion Sort method in the python program to sort an array. The time complexity of binary insertion sort is O(log n) and the space complexity is O(1).