The Simple Sorts
Selection sort and insertion sort are the two sorts people invent without being taught. Both cost about n squared over 2 comparisons in the bad case: 500 billion for a million items, over eight minutes at a billion comparisons a second. That n squared is why neither is anyone's default sort.
And yet insertion sort ships inside every production sort in every major language. The reason is that its cost is set by how disordered the input is, not by how large it is, and real input is often nearly in order already.
Selection Sort: Find the Smallest, Repeat
Scan the unsorted part for its minimum, swap it to the front of that part, and repeat on what remains. After the first pass the smallest item is in place, after the second the two smallest, and so on. The sorted prefix grows by one item per pass.
Selection sort always makes n times n minus one, over 2, comparisons, whatever the input looks like, because every pass scans the whole remainder even when it is already in order. Counted on 1,000 items, it made 499,500 comparisons on sorted, random and reversed input alike. What it does sparingly is write: at most n minus one swaps, one per pass, and 990 on the random thousand. That is the fewest writes of any common sort.
Insertion Sort: Slide Each Item Into Place
Take the next item and shift it left past every larger item already sorted, the way a hand of cards gets sorted. Each shift moves one larger item one place right and fixes exactly one inversion, a pair of items in the wrong order. So the work is n plus the number of inversions in the input.
That makes insertion sort's cost depend on the input's order. On 1,000 items already sorted, it made 999 comparisons and moved nothing. On random input it made about 254,000 comparisons, close to n squared over 4. On reversed input, where every pair is an inversion, it made 499,500, the full n squared over 2. And on sorted input with one pair of neighbours swapped, it made 1,000 comparisons and one move.
How Hard n Squared Hurts
At 1,000 items, n squared over 2 is half a million comparisons, a fraction of a millisecond, and nobody notices. At a million items it is 500 billion, over eight minutes at a billion comparisons a second. An n log n sort of the same million makes about 20 million comparisons, a fiftieth of a second at the same rate. Chapter 1 called this the gap between growth classes; here it is the gap between a sort that finishes and one that times out.
No constant closes that gap. A quadratic sort a hundred times faster per comparison still loses to an n log n sort by a factor of 250 at a million items. The curve ends the project, not the constant.
Where Insertion Sort Wins
Below a few dozen items, insertion sort's tight loop, sequential memory access and zero setup beat any recursive sort, whose splitting and bookkeeping cost more than the sorting itself at that size. On nearly sorted input, a log with a few late lines or a leaderboard after one score changed, it runs close to linear, because there are few inversions to fix.
Both facts are why every production sort hands small ranges and short runs to insertion sort, as Sorting in the Real World shows. CPython's sort, Java's, and GCC's C++ sort all finish their small pieces this way.
Production versions often add one refinement. Because the items to the left are already sorted, the place for the next item can be found by binary search, which the first topic of this chapter describes, instead of by comparing with each neighbour in turn. That cuts the comparisons for each item to about the logarithm of the prefix length. It does not cut the moves: every larger item still has to shift one place right. CPython's sort uses this binary insertion sort for its short runs, because in Python a comparison can call arbitrary user code and is expensive, while moving a pointer inside a list is cheap.
Stable and in Place
Insertion sort is stable: items with equal keys stay in their original order, because an item stops sliding as soon as it meets one that is not larger. It is also in place: it needs no memory beyond the array and one held item.
The textbook selection sort is in place but not stable. Its long-distance swap can jump an item over its equals: swapping the minimum to the front sends the front item to wherever the minimum was, past any items equal to it. That matters as soon as data is sorted by one key after another, which the next topic explains.
Quadratic Without Writing a Sort
Almost nobody writes a sort by hand any more, and the n squared still arrives, in disguise. Taking the minimum of a list and removing it, in a loop, is selection sort. Inserting each new item into a sorted Python list is insertion sort with an O(n) shift per insert. Neither shows up as a sort in a profile.
Measured on Python 3.15, the min-and-remove loop took 7 milliseconds on 1,000 items, 0.7 seconds on 10,000 and 2.8 seconds on 20,000: ten times the data, a hundred times the time. A function that takes a millisecond on a 1,000-row test fixture takes about 17 minutes on production's million rows. A thousand times the data is a million times the work.
- "Bubble sort is the simple sort to use on small arrays." It performs a three-write swap for every inversion where insertion sort performs one shift, and keeps comparing across full passes. The small-array sort inside real libraries is insertion sort; bubble sort lives on only in teaching.
- "Quadratic is fine, our lists are small." Lists grow with the business, and a quadratic step grows a millionfold when the data grows a thousandfold. The test fixture never shows it.
- "Insertion sort is always n squared." It is n plus the number of inversions. On already sorted input it makes n minus one comparisons and moves nothing, which beats any n log n sort.
- "Selection sort's fixed n squared makes it useless." It does at most n minus one swaps, so where a write costs far more than a read it minimizes the expensive operation. In RAM that is rarely the case, but the trade is real.
- "Calling the built-in sort means the code has no quadratic path." One call to sort is n log n. An O(n) sorted insert or a min-and-remove inside a loop over n items is n squared with no sort call anywhere in the profile.
- Call the language's built-in sort instead of writing one. It already contains insertion sort wherever insertion sort wins.
- Collect all the items first and sort once, rather than keeping a list sorted item by item. One n log n replaces n inserts at O(n) each.
- Test data-dependent code at production size, not fixture size. A quadratic path is invisible at 1,000 rows and fatal at a million.
- Count on cheap sorting of nearly sorted data only from an adaptive sort. Insertion sort and Timsort profit from existing order; selection sort and heapsort do not.
Knowledge Check
Insertion sort runs on a million items that are already sorted. Roughly how many comparisons does it make?
- About 500 billion, since insertion sort is always quadratic
- About 20 million, like any efficient general-purpose sort
- About a million, one per item, and it moves no items at all
- About 250 billion, a quarter of the full quadratic count
A quadratic routine takes 1 millisecond on a 1,000-row test fixture. About how long does it take on a million production rows?
- About 1 second, a thousand times longer for a thousand times the data
- About 20 milliseconds, since the slowdown is only logarithmic in n
- About 17 minutes, a million times the work of the fixture run
- About 3 hours, because larger lists also miss the processor cache more
A function repeatedly takes the minimum of a list and removes it, until the list is empty. It never calls a sort. What is its cost?
- O(n), because each minimum and each remove is a single call
- O(n log n), because the list gets shorter with every iteration
- O(n²), because it is selection sort in disguise
- O(1) per item, because Python's min is written in C
Why does every production sort still contain insertion sort?
- It is the only sort that works on arrays smaller than 64 items
- It beats recursive sorts on tiny ranges and on nearly sorted data
- It is the only stable sort that needs no extra memory at all
- It uses the fewest writes, which matters most on modern RAM
Which simple sort makes the fewest writes, and when does that matter?
- Insertion sort, because it moves each item exactly once
- Bubble sort, because it only swaps adjacent items when needed
- Selection sort, and it matters most for data held in fast RAM
- Selection sort, where a write costs far more than a read
You got correct