Toptal connects the top 3% of freelance developers all over the world.

Insertion Sort

Animation, code, analysis, and discussion of insertion sort on 4 initial conditions.

← Back to all algorithms and initial conditions

0shares

How to use: Press "Play all", or choose the Play button.

Play All	Play animation Random	Play animation Nearly Sorted	Play animation Reversed	Play animation Few Unique

ALGORITHM

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--)
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

DISCUSSION

Although it is one of the elementary sorting algorithms with O(n²) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).

For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

KEY

Black values are sorted.
Gray values are unsorted.
A red triangle marks the algorithm position.

PROPERTIES

Stable
O(1) extra space
O(n²) comparisons and swaps
Adaptive: O(n) time when nearly sorted
Very low overhead

Preparing for a technical interview? Check out our interview guides.