Insertion Sort using Binary Search in Python

English: an example on insertion sort (Photo credit: Wikipedia)

Sorting is a very essential concept in programming and Computer Science. There are different types of sorting algorithms available. Today in this post I will share a code which demonstrates Insertion sort. But unlike the default linear search being used in the algorithm I have used binary search to perform the searching. The following code gives the little example of Insertion Sort using Binary Search. The code has been written in Python.

Linear search takes O(n) to search for an element where as binary search takes O(log n) number of comparisons to search an element. Asymptotically Binary Insertion Sort is no better than linear insertion sort in worst case scenario. But the the latter has few comparisons of Order O(nlog n)

In best case Linear insertion sort is better since it will take O(n) comparisons where as binary insertion sort takes O(nlog n)

Here's the code :-