Elementary sorting

Binary search needs its array in order, and nothing so far puts it there, so this lesson builds the three obvious methods and measures exactly how far they get.

Selection sort: the fewest possible moves

The first idea most people have is also the most direct. Find the smallest element and put it first. Find the smallest of what remains and put it second. Repeat.

Concretely, for $i$ from 0 to $n - 2$ , scan the range from $i$ to $n - 1$ for the minimum and swap it into position $i$ . After round $i$ the first $i + 1$ positions hold the $i + 1$ smallest elements in order, which is the invariant, and after $n - 1$ rounds the array is sorted.

The comparison count is exact and unconditional. Round $i$ compares the current minimum against $n - 1 - i$ candidates, so the total is

\sum_{i = 0}^{n - 2} (n - 1 - i) = \frac{n (n - 1)}{2}

the same sum as the duplicate check two lessons ago: 499,500 comparisons for a thousand elements. Selection sort does exactly that many on every input of size $n$ . Already-sorted input, reverse-sorted input, random input: identical work. Best case equals worst case equals average case, which is unusual and not a virtue, since it means the algorithm cannot notice that its job is already done.

What it does minimise is data movement. At most one swap per round, so at most $n - 1$ swaps, $Θ (n)$ rather than $Θ (n^{2})$ . That is the one situation where selection sort is the right answer: when comparisons are cheap and moving an element is very expensive, as when sorting large records in place rather than sorting an array of pointers to them.

Insertion sort, and what it is really counting

The second idea is how people sort a hand of cards. Take the elements one at a time and insert each into its place among the ones already sorted, shifting the larger ones right to make room.

For $i$ from 1 to $n - 1$ , hold $a [i]$ aside as the key, then walk backwards from $i - 1$ shifting every element greater than the key one slot right, and drop the key into the gap. The invariant is that $a [0.. i - 1]$ is sorted at the start of round $i$ , which it is at $i = 1$ because a single element is sorted.

Unlike selection sort, the work depends heavily on the input. On already-sorted input each key is compared once with its predecessor, fails the test immediately, and stays put: $n - 1$ comparisons, zero moves, $Θ (n)$ total. On reverse-sorted input every key travels the whole way to the front: $n (n - 1) / 2$ comparisons and as many moves. Between those extremes the cost is governed by one quantity, and naming it is the point of this section.

An inversion of an array is a pair of positions $i < j$ with $a [i] > a [j]$ : a pair that is in the wrong relative order. A sorted array has zero inversions. A reverse-sorted array has $n (n - 1) / 2$ , the maximum, since every pair is wrong. And a random permutation has, on average, exactly half the maximum, $n (n - 1) / 4$ , because for each of the $n (n - 1) / 2$ pairs the two orders are equally likely.

Here is the connection. Each move insertion sort makes shifts one element past the key, and that shift removes exactly one inversion, since the pair was out of order before and in order after. No move removes more than one and none removes fewer, so

moves = I

exactly, where $I$ is the number of inversions in the input. The comparisons are the moves plus at most one extra per round, so they are at most $I + n - 1$ .

That is a much sharper statement than "insertion sort is $Θ (n^{2})$ ". It says the cost is linear in the disorder, so an array that is nearly sorted, meaning $I = O (n)$ , is sorted in linear time. It also explains why the average is quadratic: a random array has $n (n - 1) / 4$ inversions, about 250,000 for a thousand elements, so the average cost is half the worst case rather than a different shape.

Example. Run insertion sort on 5, 2, 4, 6, 1, 3. How many inversions does the input have, and how many moves and comparisons does the sort make?

The inverted pairs are (5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3): nine of them. Insertion sort makes exactly nine moves, as predicted. The comparisons number 12: the nine that caused a move, plus one wasted comparison at the end of each of the three rounds whose key did not travel all the way to the front.

Now you. How many inversions are in 2, 3, 5, 7, 11, 4, and how many moves will insertion sort make?

Answer

The only inverted pairs are (5,4), (7,4) and (11,4): three. So insertion sort makes exactly three moves. Comparisons are eight: three that shifted, plus one terminating comparison in each of the five rounds. An array of six elements that is one element away from sorted costs about as much as a linear scan, which is the adaptivity that keeps insertion sort in every serious library.

Bubble sort, and why it is the worst of the three

The third idea is to repeatedly sweep the array, swapping any adjacent pair that is out of order, until a whole sweep makes no swap. After the first sweep the largest element has been carried to the end, after the second the next largest, and so on, which is where the name comes from.

Bubble sort makes the same $n (n - 1) / 2$ comparisons in the worst case, and its swaps also equal the inversion count, since each adjacent swap fixes exactly one inversion. With the early-exit check it is $Θ (n)$ on already-sorted input, so it is adaptive too. On every other input it loses to insertion sort, because it performs a full swap, three assignments, where insertion sort performs one shift, and it re-examines pairs that insertion sort has already settled.

It is worth being direct about this, because bubble sort is taught more than any other sort and used less than any. Knuth's verdict in The Art of Computer Programming is that it has nothing to recommend it except its catchy name and the fact that it leads to some interesting theoretical problems. There is no input and no machine on which bubble sort is the best of the three. Learn it to recognise it, and reach for insertion sort.

Stability, and why it is not a detail

A sort is stable if elements that compare equal keep their original relative order. Selection sort as described is not stable, because the long-range swap can jump one element over an equal one. Insertion sort is stable, provided the shifting test is strictly "greater than" rather than "greater or equal", since then an incoming key stops as soon as it meets an equal element and settles after it. Bubble sort is stable for the same reason.

Stability sounds like pedantry until you need to sort by two keys. Suppose a table of employees is to be ordered by department, and within each department by surname. With a stable sort the job is two passes: sort by surname, then sort by department. The second sort moves whole departments into place and, being stable, leaves the surname order inside each department untouched. With an unstable sort that trick does not work at all and you must write a comparison function that compares both fields, which is more code and, more importantly, has to be changed every time the user picks a different column to sort by. This is exactly why spreadsheet and table-view sorting is specified as stable.

The cost of stability is real: the fastest in-place sorts, quicksort and heapsort, are both unstable, and the standard stable sort, mergesort, needs extra memory. Language libraries split on the question. Java's Arrays.sort on objects is Timsort and stable, while on primitives it is a dual-pivot quicksort and unstable, on the grounds that two equal integers are indistinguishable so nobody can tell. C++ offers std::sort (unstable, fast) and std::stable_sort separately, which is the honest interface.

Example. A list holds (Ada, Engineering), (Bo, Sales), (Cy, Engineering), (Di, Sales) in that order. It is sorted by name, then by department, with a stable sort. What comes out?

Sorting by name gives Ada, Bo, Cy, Di. Sorting that by department moves both Engineering rows ahead of both Sales rows, and stability preserves the name order within each group, giving (Ada, Engineering), (Cy, Engineering), (Bo, Sales), (Di, Sales). Names ascend inside each department without any comparison function ever mentioning names and departments together.

Now you. The same list, sorted first by department and then by name, with a stable sort. What comes out, and what does that tell you about the order of the passes?

Answer

Sorting by department gives Ada, Cy, Bo, Di. Sorting that by name gives Ada, Bo, Cy, Di, with departments interleaved: the department grouping is destroyed. The rule is that the last sort is the primary key, so passes must run from the least significant key to the most significant. Getting this backwards is the standard bug, and the same principle reappears in radix sort three lessons from now.

The wall, in seconds

The three algorithms differ in constants and in adaptivity, and not at all in shape: all are $Θ (n^{2})$ in the average and worst cases. It is worth seeing what that costs, on a machine doing $10^{9}$ comparisons a second.

$n$	quadratic sort	$n \log_{2} n$ sort
1000	0.5 ms	10 µs
$10^{4}$	50 ms	133 µs
$10^{5}$	5.0 s	1.7 ms
$10^{6}$	8.3 minutes	20 ms
$10^{7}$	14 hours	233 ms

At a thousand elements the difference is invisible and the simpler code wins. At a million it is eight minutes against a fiftieth of a second, and at ten million the quadratic sort has left the range of things anyone waits for. The wall arrives somewhere in the tens of thousands, and it arrives suddenly, which is the usual way a program that worked in testing fails in production.

Example. An insertion sort takes 5.0 seconds on 100,000 random records. A colleague suggests running it on 400,000. How long, and what would a machine four times faster achieve?

Cost scales as $n^{2}$ on random input, and $n$ grew by a factor of 4, so the work grows by 16: about 80 seconds. A machine four times faster brings that back to 20 seconds, still four times the original. The alternative is to change the shape: an $n \log_{2} n$ sort on 400,000 elements is about $7.4 \times 10^{6}$ comparisons, roughly 7 milliseconds, which is four orders of magnitude better than anything the hardware could buy.

Now you. The same insertion sort is instead given 400,000 records that are already nearly sorted, with about 300,000 inversions in total. Roughly how long?

Answer

Insertion sort's moves equal the inversion count, so the work is about $300 {,} 000 + 400 {,} 000 = 700 {,} 000$ operations rather than the $4 \times 10^{10}$ that random input of that size would need. At the same rate that the 100,000-element run implies, roughly $10^{10}$ operations in 5 seconds, this takes well under a millisecond. Nearly sorted input is not a slightly easier case for insertion sort; it is a different complexity class.

Why quadratic is unavoidable here

Every one of these three algorithms shares a structural feature: they compare and move adjacent or nearly adjacent elements. Insertion sort and bubble sort remove exactly one inversion per move, and a random array has $Θ (n^{2})$ inversions, so any algorithm that removes inversions one at a time is stuck at $Θ (n^{2})$ no matter how cleverly it is coded. This is not a limitation of the implementations; it is a limitation of the strategy.

Escaping it therefore requires moves that fix many inversions at once, which means comparing elements that are far apart. Selection sort's long-range swap does move elements far, but it learns nothing from the comparisons it makes along the way: each round rediscovers order it already had evidence for, throwing away $n$ comparisons to place a single element.

So the requirement for something better is an algorithm that both moves elements over long distances and keeps what its comparisons told it. The next lesson supplies a general strategy that does both by attacking the array's size directly, splitting the problem rather than the array's disorder, and it produces the first sort with a guaranteed $Θ (n \log n)$ bound.