In this tutorial, we’ll present Binary Insertion Sort. It’s a variant of Insertion Sort that uses Binary Search to improve performance.
2. Insertion Sort
Insertion Sort sorts the input array by iteratively growing a sorted sub-array at the start of .
So, Insertion Sort first checks if and swaps them if that’s the case. Then, it finds where it should insert so that it holds that ( is the -th element of , whereas is the initial value of ). It continues like this, growing the sorted sub-array one element at a time. Before it inserts , the sorted sub-array consists of the elements initially at positions through but now in the sought order:
Insertion Sort inserts right at the place that makes also sorted. When it inserts at the appropriate position, the whole array becomes non-descending.
This is the pseudo-code of Insertion Sort:
2.1. The Complexity of Insertion Sort
The worst-case input is an array sorted in the opposite way (). In that case, Insertion Sort has to do comparisons and swaps for each . In total, it does swaps and performs the same number of comparisons. Therefore, the algorithm has the quadratic worst-case time complexity.
The average-case complexity of Insertion Sort is also .
3. Binary Insertion Sort
The idea behind Binary Insertion Sort is to use Binary Search to find where to place each . The goal is to reduce the number of comparisons.
This is the pseudo-code of BIS:
3.1. The Complexity of Binary Insertion Sort
The number of swaps is the same as in the standard version of Insertion Sort.
In the worst case, we perform approximately comparisons for each , and do exactly one comparison for :
Using Stirling’s approximation, we get:
So, we conclude that the number of comparisons Binary Insertion Sort performs is log-linear in . However, since the number of swaps is , both algorithms are asymptotically the same in the worst case. That’s also true of their average-case complexities.
4. When to Use Binary Insertion Sort?
Why should we bother implementing binary search and using it within Insertion Sort if the resulting complexity doesn’t change? It seems Binary Insertion Sort isn’t worth the extra work. The answer is that, although asymptotically equivalent to the standard version of Insertion Sort, Binary Insertion Sort usually works faster in practice. It compares fewer elements because of binary search.
If the elements are complex, and comparing two objects takes a lot of time, the time spent comparing the items will dominate that spent exchanging them. In such cases, the improvement brought by binary search pays off significantly. If we deal with simple types such as numbers of characters, we probably won’t notice any difference. However, in most real-world applications, our data will be more intricate.
In this article, we talked about Binary Insertion Sort. It’s a variant of Insertion Sort that uses Binary Search to find where to place in the input’s sub-array while iterating over .
Although Binary Search reduces the number of comparisons to in the worst case, Binary Insertion Sort has a quadratic time complexity just as Insertion Sort. Still, it is usually faster than Insertion Sort in practice, which is apparent when comparison takes significantly more time than swapping two elements.