AlgoScope

Insertion Sort

Take the next value and slide it left past larger values into the sorted prefix.

Sorting, algorithm, beginner
Comparing 5 at index 0 with 1. 5 is larger, so 1 moves to index 0.sorted 0-010514223843576ji5 > 1
Comparing 5 at index 0 with 1. 5 is larger, so 1 moves to index 0.sorted 0-010514223843576ji5 > 1

Insertion Sort: Seven values

Decision, step 3 of 27

5 is larger than 1, so 1 slides left.

Cost

Best
O(n)
Average
O(n^2)
Worst
O(n^2)
Space
O(1)

Fast on nearly sorted input. The standard choice for tiny arrays.

Properties

  • Yes: Comparison based
  • Yes: Stable
  • Yes: In place
  • Yes: Adaptive
  • Yes: Online

Leads to

Topics that need this one first.

Taught by the same lesson

Insertion Sort covers these too, in the same run.