Insertion Sort

Pick up each element and slide it into its correct position — like sorting a hand of cards

Speed: 400ms
Pass: 0 Comparisons: 0 Shifts: 0
Sorted region
Key (picked up)
Comparing
Shifting right
Unsorted
Press Step or Play to begin Insertion Sort

How Insertion Sort Works

Insertion Sort builds the sorted portion one element at a time. It picks the next unsorted element (the "key") and slides it leftward past any larger elements until it finds its correct position — just like inserting a playing card into a sorted hand.

for i = 1 to n-1:
  key = arr[i] // pick up this card
  j = i - 1
  while j ≥ 0 and arr[j] > key:
    arr[j+1] = arr[j] // shift larger element right
    j = j - 1
  arr[j+1] = key // insert key into correct slot

Time complexity: Best case O(n) when the array is already sorted (each element compared once, no shifts needed). Average and worst case O(n²) — worst case occurs when the array is in reverse order.

Space complexity: O(1) — sorts in place, only needs a temporary variable to hold the key.

Key insight: The sorted region grows from left to right. At each step, everything to the left of the key is already sorted. Elements larger than the key shift one position right to make room.