Binary Insertion Sort Visual Guide | Draftsbook

Basic Sorting · Article 5 of 62

Binary Insertion Sort

Insertion Sort with a smarter probe: use binary search to find where the new element belongs in O(log n), then shift.

How it works

Plain Insertion Sort does up to i comparisons to find the insertion point for element i. Binary Insertion Sort replaces that linear probe with a binary search over the sorted prefix.

Pick the next element as the key.
Binary-search the sorted prefix arr[0..i-1] for the leftmost position where the key would still respect order.
Shift the suffix one slot right.
Insert the key in the freed slot.

The total comparison count drops from Θ(n²) to Θ(n log n) — useful when comparisons are very expensive (think: comparing long strings). The shift step, however, is still Θ(n²) writes in the worst case.

Complexity

Best time

O(n log n) cmp · O(n²) writes

Average time

O(n²)

Worst time

O(n²)

Extra space

O(1)

Stable

Yes

In-place

Yes

Java's old Arrays.sort for object arrays once used binary insertion sort for small runs — comparisons there involve calling compareTo, so cutting them was worth the extra shift work.

Interactive visualization

Pseudocode

procedure binaryInsertionSort(A):
  for i from 1 to n − 1:
    key ← A[i]
    pos ← binarySearch(A, 0, i, key)
    shift A[pos..i − 1] right by 1
    A[pos] ← key

JavaScript implementation

function binaryInsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let lo = 0, hi = i;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid] <= key) lo = mid + 1;
      else hi = mid;
    }
    for (let j = i; j > lo; j--) arr[j] = arr[j - 1];
    arr[lo] = key;
  }
  return arr;
}

Pros and cons

Pros

Cuts comparisons to O(n log n) — big win when comparisons are costly.
Stable when the search uses an upper-bound (lower-bound + key <=) probe.
Still in-place; constant extra memory.

Cons

Shift cost is still O(n²) writes worst case.
Slightly more complex than plain insertion sort.
Loses when comparison cost is cheap relative to memory writes.

When to use it

Sorting object arrays with expensive comparators.
Small runs in hybrid sorts when comparisons dominate.
Stability + low comparison count is required and the array is small.

Up next: Shell Sort — a recursive divide-and-conquer sort that always runs in O(n log n) and never quadratic.

Binary Insertion Sort: Mechanism, Complexity Analysis & Interactive Visualizer