# Binary Insertion Sort

# Binary Insertion Sort

Binary insertion sort improves insertion sort by using binary search to locate the correct insertion position in the sorted prefix. This reduces the number of comparisons, though element shifting still dominates the runtime.

The algorithm keeps the same structure as insertion sort but replaces the linear scan with a logarithmic search.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

## Algorithm

For each element $A[i]$, use binary search on the sorted prefix $A[0..i-1]$ to find its correct position, then shift elements to insert it.

```id="k4p9x2"
binary_insertion_sort(A):
    n = length(A)
    for i from 1 to n - 1:
        key = A[i]

        left = 0
        right = i

        while left < right:
            mid = (left + right) // 2
            if A[mid] <= key:
                left = mid + 1
            else:
                right = mid

        for j from i downto left + 1:
            A[j] = A[j - 1]

        A[left] = key
```

## Example

Let

$$
A = [5, 2, 4, 6, 1]
$$

Step 1:

Insert 2 into [5]

→ [2,5,4,6,1]

Step 2:

Insert 4 into [2,5] using binary search

→ [2,4,5,6,1]

Step 3:

Insert 6 into [2,4,5]

→ [2,4,5,6,1]

Step 4:

Insert 1 into [2,4,5,6]

→ [1,2,4,5,6]

## Correctness

At each iteration, binary search identifies the correct insertion position within the sorted prefix. Shifting elements preserves order, and inserting the key maintains sorted structure. The invariant that the prefix is sorted holds for all iterations.

## Complexity

| case    | comparisons               | time     |
| ------- | ------------------------- | -------- |
| best    | $O(n \log n)$ comparisons | $O(n^2)$ |
| worst   | $O(n \log n)$ comparisons | $O(n^2)$ |
| average | $O(n \log n)$ comparisons | $O(n^2)$ |

Shifting dominates cost:

$$
O(n^2)
$$

Space complexity:

$$
O(1)
$$

## Properties

* stable
* in-place
* fewer comparisons than insertion sort
* same asymptotic time due to shifts

## When to Use

Binary insertion sort is useful when comparisons are expensive but memory moves are relatively cheap. It also appears in hybrid sorting algorithms where reducing comparison count matters.

## Implementation

```id="m8x2q4"
def binary_insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]

        left, right = 0, i
        while left < right:
            mid = (left + right) // 2
            if a[mid] <= key:
                left = mid + 1
            else:
                right = mid

        for j in range(i, left, -1):
            a[j] = a[j - 1]

        a[left] = key

    return a
```

```id="p7k3z1"
func BinaryInsertionSort[T constraints.Ordered](a []T) {
    for i := 1; i < len(a); i++ {
        key := a[i]

        left, right := 0, i
        for left < right {
            mid := (left + right) / 2
            if a[mid] <= key {
                left = mid + 1
            } else {
                right = mid
            }
        }

        for j := i; j > left; j-- {
            a[j] = a[j-1]
        }

        a[left] = key
    }
}
```