Summary

Binary Insertion Sort improves upon standard Insertion Sort by minimizing the number of comparisons. Instead of linearly scanning backwards to find the insertion point, it uses Binary Search on the already-sorted portion of the array. While this reduces the comparison complexity to $O(n \log n)$, the algorithm still requires $O(n^2)$ write operations to shift elements to make room for the insertion.

How it Works

• Assume the first element is a sorted sub-array.

• Select the next element as the key.

• Perform a Binary Search on the sorted sub-array to find the index of the first element greater than the key.

• Shift all elements from that index onwards one position to the right to create a gap.

• Insert the key into the gap.

• Repeat until the entire array is sorted.