Insertion Sort

Builds a sorted prefix one element at a time, shifting larger values right to make room — exactly how people sort playing cards. Nearly O(n) on almost-sorted data.

Category: Sorting
Time complexity: O(n²)
Space complexity: O(1)

Pseudocode

A[0] is sorted
for i ← 1..n−1: key ← A[i]
  shift larger sorted items right
  insert key into the gap
done

Reference implementation

for i in range(1, n):
    key = a[i]; j = i - 1
    while j &gt;= 0 and a[j] &gt; key:
        a[j + 1] = a[j]; j -= 1
    a[j + 1] = key

Open the interactive Insertion Sort visualisation →