Binary insertion sort
Binary insertion sort is ordinary insertion sort with one change: instead of scanning left from the current position to find where a value belongs, it binary searches the already-sorted prefix for that position. Once the position is found, it still has to shift every value between that point and the current position one place right to make room, exactly as plain insertion sort does.
When it is the right choice
It is worth using over plain insertion sort specifically when comparisons are expensive relative to moving values — comparing long strings or calling a costly comparator function, for instance — since it cuts comparisons from O(n) to O(log n) per insertion. It buys nothing when comparisons are cheap: the shifting that dominates insertion sort's cost on large or reversed arrays is exactly as expensive here, so its worst-case running time is still O(n²).
How it works
- For each position from the second item to the last, remember its value as the one being inserted.
- Binary search the already-sorted prefix to its left: repeatedly check the midpoint of the remaining range.
- If the midpoint value is greater than the one being inserted, search the half below it; otherwise search the half above it.
- Once the search range is empty, its lower bound is the position the value belongs at.
- Shift every value from that position up to the current one along by one place to the right, then place the remembered value into the gap.
Worth noticing
- Its comparisons drop sharply relative to plain insertion sort, but its writes do not change at all — the same values get shifted the same distance either way, since binary search only changes how the insertion point is found, not how values get moved once it is.
- Its comparison count does not adapt to nearly-sorted input the way plain insertion sort's does: a linear scan can stop after one comparison when a value is already in place, but binary search always pays its full O(log i), sorted or not.
- It is stable, for the same reason plain insertion sort is: the binary search here finds the position after the last equal value, so equal values keep their original relative order.
Cost
- Best
- O(n log n)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- Yes