Lesson 19 · Algorithms

Sorting

Putting things in order is one of the most common jobs a program does, because sorted data is far easier to search and use. Watch eight numbers in a row of memory get sorted twice: once by insertion sort, which shifts items one slot at a time, and once by merge sort, which splits the row and merges it back. Then see why it matters that a sort is stable, and what Python's sorted() really does.

11 min10 steps5 questionsIntermediate

Fig 19 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01Insertion sort is about to insert the key 4 into the sorted part [2, 5, 7]. What happens?

Insertion sort compares the key with the items on its left, shifts every bigger one (7, then 5) one slot right, and drops the key into the gap: [2, 4, 5, 7].

02Roughly how does insertion sort's worst-case work grow if you double the number of items?

Insertion sort is O(n²): its worst case is n(n−1)/2 comparisons, so doubling n makes the work about four times bigger.

03Merge sort is merging the runs [1, 6] and [3, 4]. Which item goes into the spare row first?

A merge only compares the front item of each run: 1 against 3. The smaller one, 1, is copied first; then 3 against 6, and so on.

04What does it mean that a sort is stable?

Stable means ties keep their original order. That is why sorting people by age keeps people of the same age in the order you had them.

05Which statement about Python's sorted() is true?

sorted() returns a new list and uses Timsort: it finds runs, extends short ones with insertion sort and merges them. The Python docs guarantee it is stable; list.sort() sorts in place.

Key terms

Glossary

Sorting: Putting items in order, such as numbers from smallest to largest.
Insertion sort: A sort that grows a sorted part on the left, inserting each next item into its place by shifting bigger items right.
Merge sort: A divide-and-conquer sort: split the list in halves until each piece has one item, then merge sorted pieces back together.
Merge: Combining two sorted runs into one by repeatedly taking the smaller of their two front items.
Run: A stretch of items that is already in order.
O(n²) and O(n log n): Ways to say how work grows with the number of items n: n² grows much faster than n × log₂ n.
Stable sort: A sort that keeps items that compare equal in their original order.
Timsort: The sort CPython uses for sorted() and list.sort(): it finds runs, extends short ones with binary insertion sort and merges them.

Fine print

Notes and sources

O(n²) and O(n log n) describe how the work grows as the number of items n grows, ignoring constant factors. log₂ n is how many times n can be halved before reaching 1 (log₂ 8 = 3).
Insertion sort is fast on small or nearly sorted lists: on an already sorted list it makes only n − 1 comparisons and moves nothing.
Merge sort always splits evenly, so its worst case is O(n log n) too; for 1,000 items it needs at most 8,977 comparisons. It needs a spare row (extra memory) for merging.
CPython's sort uses binary insertion sort to build short runs, so for fewer than 64 items it is binary insertion sort alone. Since Python 3.11 it decides the order of merges with Munro and Wild's powersort policy.
The marks a and b are only labels in the drawing so you can tell the two 5s apart; Python sees two equal 5s.

Quiz Unlocks after the last step.