Binary insertion sort cuts comparisons to O(n log n) — so why isn't its running time O(n log n)?

## Two different costs wearing one name Every insertion into a sorted contiguous region has two parts: 1. **Search** — where does this element belong? 2. **Move** — make a hole there. Plain insertion sort fuses them: the backward scan compares and shifts in the same step, so both costs are `O(i)` on pass `i`. Binary insertion sort separates them, replacing the linear search with a binary search over the sorted prefix and then doing the shifting as a separate loop. The improvement is real but partial, and the trap is to price only the half that got cheaper. ## The arithmetic - **Comparisons.** Binary search over a prefix of size `i` costs `⌈log2(i + 1)⌉` comparisons. Summed over `i = 1..n-1` this is `Θ(n log n)`, and — importantly — it is `Θ(n log n)` on *every* input, best case included. - **Moves.** The element inserted at position `p` of a prefix of size `i` requires `i - p` shifts. Worst case (reversed input) `p = 0` every time, giving `0 + 1 + 2 + ... + (n-1) = n(n-1)/2` moves. - **Total time.** `Θ(n log n) + Θ(n^2) = Θ(n^2)`. So the improvement is a constant-ish win on the comparison side only. It is worth something when comparisons are genuinely expensive relative to moves — comparing long text keys or calling a costly comparison function — and worth nothing when the elements are small and the moves dominate, which is the common case. ## The best case gets worse, not better This is the part candidates almost never mention, and it is the sharpest point in the topic. On already-ordered input: | Variant | Comparisons | Moves | Time | |---|---|---|---| | Plain insertion sort | `n - 1` | 0 | `Θ(n)` | | Binary insertion sort | `Θ(n log n)` | 0 | `Θ(n log n)` | Binary search has no early exit — it always runs its full logarithmic descent, even when the answer is "right where it already is". So the variant that looks strictly better on paper destroys the single property that makes insertion sort worth keeping: adaptivity on nearly-ordered data. If your reason for choosing insertion sort in the first place is that your input arrives almost in order, binary insertion is a downgrade. ## Stability needs the right search Binary search finds *a* valid position, and when the prefix contains elements equal to the key there is a range of valid positions. To preserve stability the search must return the position **after the last equal element** (the upper bound), so the newly inserted element ends up behind equal elements that arrived earlier. A search that returns the first match, or whatever midpoint it happens to hit, will sometimes place the key ahead of an equal predecessor and quietly break stability — a defect no ordering assertion will catch, because the output is still sorted. ``` for i in 1..n-1 key = a[i] lo = 0 hi = i while lo < hi mid = (lo + hi) / 2 if a[mid] <= key lo = mid + 1 else hi = mid ... ``` The `<=` in that test is what pushes the position past equal elements; with `<` it would stop at the first equal one and the sort would no longer be stable. ## The general lesson The reason this question is asked is not that anyone ships binary insertion sort. It is that it catches a habit: pricing an algorithm by the one operation named in the analysis you remember. Comparison counts and move counts are separate budgets, and an optimisation that improves one can leave the total untouched — or, as here, make a different case worse. The same discipline applies whenever you propose a change: name every cost the workload actually pays, and check which one dominates before claiming an improvement. Cutting the cheap half of the work in half is not a speedup. A genuinely different way to escape the quadratic move cost is to change the storage so that insertion does not require shifting a contiguous block — but that is a data-structure change, not an insertion-sort optimisation, and it gives up the in-place, cache-friendly behaviour that is the algorithm's remaining advantage.