# Insertion Sort with Sentinel

# Insertion Sort with Sentinel

Insertion sort with sentinel is a small optimization of insertion sort. It first places the minimum element at the beginning of the array. That element acts as a sentinel, so the inner loop can stop without checking whether it has reached the start of the array.

You use it when implementing insertion sort as a low-level routine, especially inside hybrid sorts.

## Problem

Given an array ( A ) of length ( n ), sort it in place using insertion sort while reducing inner-loop branch checks.

## Idea

Standard insertion sort checks two conditions in the inner loop:

```id="4kz91p"
while j >= 0 and A[j] > x:
```

After moving the minimum element to ( A[0] ), the scan must stop there because no element can be smaller. The bounds check can be removed:

```id="p8r2ma"
while A[j] > x:
```

## Algorithm

```id="8s2qnx"
insertion_sort_with_sentinel(A):
    n = length(A)
    if n <= 1:
        return A

    min_index = 0
    for i in 1..n-1:
        if A[i] < A[min_index]:
            min_index = i

    swap(A[0], A[min_index])

    for i in 2..n-1:
        x = A[i]
        j = i - 1

        while A[j] > x:
            A[j + 1] = A[j]
            j = j - 1

        A[j + 1] = x

    return A
```

## Example

Input:

[
A = [5, 3, 4, 1, 2]
]

First move the minimum to the front:

[
[1, 3, 4, 5, 2]
]

Now insertion sort proceeds from index 2. The sentinel ( 1 ) prevents the scan from moving past the start.

Final result:

[
[1, 2, 3, 4, 5]
]

## Correctness

The smallest element is placed at index 0. During insertion, any backward scan must stop at or before this sentinel because no inserted value can be smaller than it.

The remaining insertion sort logic preserves the sorted prefix. After each iteration, ( A[0..i] ) is sorted. After the final iteration, the whole array is sorted.

## Complexity

| case    | time       |
| ------- | ---------- |
| best    | ( O(n) )   |
| average | ( O(n^2) ) |
| worst   | ( O(n^2) ) |

Space:

[
O(1)
]

The sentinel optimization improves constant factors, not asymptotic complexity.

## Stability

The initial swap can break stability if equal minimum values exist. A stable version should move the first minimum to the front by shifting rather than swapping, or skip the sentinel optimization when stability is required.

## When to Use

Use insertion sort with sentinel when:

* sorting small arrays
* implementing a hybrid sort base case
* branch reduction matters
* stability is not required

It is a practical micro-optimization for performance-sensitive sorting code.