TwiddleLab / Code / Algorithms in Motion

Insertion Sort

Lesson 4 of 11 · 7 min · Free, no account needed

What you will learn

• Insertion sort: take the next card and slide it left past every bigger card.
• Each shift fixes one pair that was out of order, so the work depends on the data.
• Best case: already sorted, no shifts, about n comparisons. Worst case: reversed, every pair shifts, n(n - 1)/2.
• Nearly sorted data, like a ranked feed with a few new posts, is where insertion sort shines.

Start the lesson

How the lesson goes

1. You pick up cards one at a time and keep your hand sorted.

   Two hands to sort. Which one will take fewer moves?

2. Sort a hand the way your brain does.

   Drag the orange card left to where it belongs. The green cards are already in order.

3. Make a hand that costs exactly 10 shifts.

   Start sorted. Tap a gap to swap the two cards beside it. Your hand races at the end.

   A shift swaps two neighbours that are out of order, which fixes exactly one such pair. So the number of shifts equals the number of pairs out of order.

4. Insertion sort.

   Insertion sort: take the next item and slide it left past every bigger one. The left part is always sorted.

   The work depends on the data. Best case: already sorted, no shifts, n - 1 comparisons.

   Worst case: reversed, every pair shifts: n(n - 1)/2, as slow as selection sort. Nearly sorted data is almost as cheap as the best case.

5. The same idea in Python. Step through it.

   Watch j slide left while the card before it is bigger.

6. Build the slide.

   The loop is ready. Add the lines that slide card j left.

7. A live feed: new posts keep arriving.

   The feed is ranked, highest score first. Slot each new post into place before the bar runs out.

8. Fast or slow for insertion sort?

   Count the pairs out of order. Drag each list into a jar.

9. Where does the orange card land?

   Tap a gap, then Check.

   The loop keeps swapping while the card before is bigger. 9, 7 and 5 are bigger than 4; 2 is not, so it stops there.

10. Race: selection against insertion.

    Two tracks: your hand from earlier, then an almost sorted one. Pick a winner before each race.

Previous lesson: Selection Sort · Next lesson: Big O: How the Bars Grow · Part of the course: Algorithms in Motion

Lessons are interactive and need JavaScript. Turn it on to play them.