Insertion sort

Sorting by maintaining a sorted prefix and inserting each new element into its correct position, with adaptive O(N) behavior on nearly sorted data.

Insertion Sort

Insertion Sort builds a sorted prefix one element at a time. In the $i$-th iteration, the first $i$ elements are already sorted. The algorithm takes the next element $a[i]$ and shifts it leftward — swapping with its left neighbor as long as that neighbor is larger — until it lands in its correct position. After the iteration, the sorted prefix grows to length $i+1$.

Example

How It Works Step by Step

For a = [5, 3, 8, 1, 9, 2]:

Adaptive Behavior

Insertion Sort is adaptive — it takes advantage of existing order in the input. When a new element is inserted, the inner loop stops as soon as it finds a smaller neighbor (the break). On an already sorted array, every element is inserted in one comparison, giving $O($ total.