Skip to content

level 3 · Sorting

Insertion Sort

How you actually sort a hand of cards, without being taught.

8 min 55 XP

what is it

Start here

Pick up one card at a time and slide it left until it's sitting in the right place among the cards you're already holding. That's insertion sort, and it's what almost everyone does with a real hand of cards without ever being taught.

The left side of the list is your tidy hand. The right side is still on the table. Each new card only has to travel as far left as it needs to — and if it's already bigger than everything in your hand, it doesn't move at all.

That's what makes it special. On a list that's nearly sorted already, insertion sort barely does any work. It is the only simple sort that gets *faster* when the data is close to correct — which is why real sorting libraries fall back to it for small or nearly-sorted chunks.

real-life analogy

Picture it

A hand of cards

You're dealt cards one by one. Each new card, you fan out what you're holding, find the gap, and slide it in. You never re-sort the whole hand — you just place the new arrival. If the cards happen to arrive in order, you place each one on the end and do nothing else.

interactive visualization

Watch it run

Try a nearly-sorted list like 1 2 4 3 5 6 and watch how little it does.

  1. 8
  2. 3
  3. 5
  4. 1
  5. 9
  6. 2
  7. 7

Think of holding cards. The left side is your tidy hand; everything to the right is still on the table. Pick up one card at a time and slide it into place.

step 01/40

  • comparing
  • moving
  • in final place
1function insertionSort(a) {
2 for (let i = 1; i < a.length; i++) {
3 let j = i;
4 while (j > 0 && a[j - 1] > a[j]) {
5 [a[j - 1], a[j]] = [a[j], a[j - 1]];
6 j--;
7 }
8 }
9 return a;
10}

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

40 steps

complexity

What it costs

best case
O(n)
average
O(n²)
worst case
O(n²)
extra memory
O(1)

Worst case (reversed input) every card travels all the way left: n²/2 moves. Best case (already sorted) every card stays put: just n−1 comparisons and zero swaps.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²) · this one
input size →work →

common mistakes

Common traps

  • Starting the outer loop at i = 0.

    Start at 1. A hand of one card is already sorted — there is nothing to compare it against.

  • Forgetting to stop as soon as the card is in place.

    The moment the card on the left is not bigger, you're done — everything further left is already smaller. Break out. Scanning on is wasted work and destroys the O(n) best case.

  • Thinking it's 'just bubble sort'.

    Bubble sort makes a full pass regardless. Insertion sort stops each card the instant it lands. On nearly-sorted data that's the difference between n² and n.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+55 XP

01What is insertion sort's best case, and when does it happen?

02What is the worst possible input for insertion sort?

03Real sorting libraries switch to insertion sort for small chunks. Why?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.