Skip to content
← Back to algorithms

Step 0 / 0 · Comparisons: 0 · Swaps: 0

How this algorithm works

How it works

  1. Treat the first element as a sorted region of size one.
  2. Take the next element from the unsorted region as the 'key'.
  3. Shift each element in the sorted region that is greater than the key one position to the right.
  4. Stop shifting once you find an element less than or equal to the key, or reach the start.
  5. Insert the key into the gap left by the shifts.
  6. Repeat, growing the sorted region by one element each time until the whole array is sorted.

Key concepts

  • Comparison-based sorting
  • Stable sort (equal elements never cross during a shift)
  • In-place (O(1) extra space)
  • Adaptive: runs in O(n) on nearly-sorted input

When to use it

When the input is small or nearly sorted, or as the base case in hybrid sorts like Timsort. Efficient for online sorting where data arrives one element at a time.

Did you know

Insertion sort is how most people sort a hand of playing cards: picking up one card at a time and inserting it into its correct position among the cards already sorted.