Binary Insertion Sort

Algorithm

Binary Insertion Sort improves the search step of Insertion Sort by using binary search to find the insertion point, rather than a linear backwards scan. The shifting step remains unchanged.

For each $j$ from 2 to $n$:

1. The prefix $A[1 \dots j-1]$ is sorted.
2. Perform binary search on $A[1 \dots j-1]$ to find the index $k$ where $A[j]$ belongs (the position where all elements before $k$ are $\le A[j]$).
3. Shift $A[k \dots j-1]$ right by one position.
4. Insert $A[j]$ at position $k$.

Where the Improvement Lies

Standard Insertion Sort uses a linear scan that performs $O(j)$ comparisons to find the insertion point for element $j$. Binary search performs $O(\log j)$ comparisons. Over all $n$ elements, comparisons drop from $\Theta(n^2)$ to:

$\sum_{j=2}^{n} \log_2 j = \log_2(n!) = \Theta(n \log n)$

Where It Does Not Help

The shifting step still moves up to $j-1$ elements on each insertion. In the worst case, every element must be shifted, requiring:

$\sum_{j=2}^{n} (j-1) = \frac{n(n-1)}{2} = \Theta(n^2)$

movements. Since each shift is a write operation, the total time is still dominated by the $\Theta(n^2)$ shifting cost. The asymptotic running time remains $\Theta(n^2)$ worst case and average case.

Comparison: Standard vs Binary Insertion

Metric	Standard Insertion Sort	Binary Insertion Sort
Comparisons	$\Theta(n^2)$	$\Theta(n \log n)$
Shifts/swaps	$\Theta(n^2)$	$\Theta(n^2)$
Overall time	$\Theta(n^2)$	$\Theta(n^2)$
Best case	$\Theta(n)$	$\Theta(n \log n)$ (binary search still costs $\log j$ each)

The best case actually becomes worse with binary insertion: even on an already-sorted array, binary search still costs $\Theta(\log j)$ comparisons per element, totalling $\Theta(n \log n)$, whereas standard Insertion Sort gets $\Theta(n)$.

When Binary Insertion Sort Is Useful

Binary insertion sort helps when:

1. Comparisons are expensive, and writes are cheap: e.g. sorting strings where each string comparison is costly but copying a pointer (the “shift”) is lightweight.
2. The data structure supports binary search but not efficient linear scan: e.g. an array where the sorted prefix is conceptually separate from the insertion machinery.

In practice, standard Insertion Sort is usually preferred because its linear scan is cache-friendly and its best case is genuinely linear.

Summary

Aspect	Detail
Search method	Binary search in sorted prefix
Comparison count	$\Theta(n \log n)$
Shift count	$\Theta(n^2)$ worst case
Overall time	$\Theta(n^2)$
Best case	$\Theta(n \log n)$ (worse than standard)
Use case	Expensive comparisons, cheap writes
Compared to standard	Reduces comparisons but does not improve asymptote