Sorting algorithms

01An ordered result needs a repeatable method

A list is a row of items in a particular order. Here each item is one card. Its value is the number we use for comparison; its position tells us where it is in the row. Moving a card changes its position, not the number written on it.

Our requirement is precise: every card must be no larger than the next card, and no card may be lost or added. Equal values are allowed beside each other. A finite set of unambiguous instructions for completing this task is an algorithm. We will study five sorting algorithms: five different ways to reach the same kind of result.

In each experiment, gold marks the cards involved in the current step. Green marks positions that will not need to change again. Letters identify the original cards, so two cards carrying 2 can still be told apart. Next step shows a decision and an explanation of its reason; continuing reveals the change it causes. Back restores the earlier state, including the counters.

02Bubble sort: carry a large value to the right

Start with just two neighbours. If the left card is larger, exchange them; otherwise keep them. Now move one position to the right and repeat. After comparing 5 with 2, the 5 moves right. When it later meets 7, the 7 becomes the larger value carried onwards. This explains why a left-to-right pass leaves the largest value at the right end.

We can now leave that final position alone and repeat over the shorter unfinished part. Why does this finish? Each completed pass fixes one more position, so a finite list cannot leave us repeating forever. If a pass makes no exchanges, every neighbour was already in order. A card is then no larger than its neighbour, which is no larger than the next one, and so on: the whole list is ordered. That lets us stop early.

03Selection sort: decide one final position at a time

We have another way to choose the first card: inspect every remaining card and remember the smallest seen so far. Begin by remembering the first one. Whenever a smaller value appears, replace the remembered choice. Only after all remaining cards have been checked do we exchange that minimum into the first unfinished position.

The remembered value really is a minimum because each inspected card was compared against it, and the remembered value only becomes smaller. After placing it, all remaining values are at least as large. Repeat on the remaining part. Notice a difference from bubble sort: even an already ordered row still needs all those inspections, because this method has no “no exchanges means finished” rule.

04Insertion sort: keep the part we have already arranged

One card by itself is already ordered. Take the next card and compare it with its left neighbour. If that neighbour is greater, exchange them and inspect the new left neighbour. Stop at the beginning or at a neighbour no greater than the chosen card. We have inserted one card into the correct place without disturbing the order of the others.

Why is stopping there sufficient? Everything farther left was already ordered, so it is no greater than the neighbour where we stopped. Everything we crossed was greater than our chosen card and has moved to its right. Both sides therefore satisfy the required order. The ordered part grows by one card each time until it includes the whole row.

05Merge sort: use two smaller completed tasks

Suppose we already have two ordered rows. To find the smallest card still unused, we need only compare their front cards: everything later in either row is at least as large as its own front. Copy the smaller front card into a new row, advance that row’s front, and repeat. When one row is empty, append the remaining cards from the other row in their existing order. This operation is called merging.

Where do the two ordered rows come from? Split the original row into two parts, and apply the same sorting task to each part. Continue splitting until each part has one card. Those smallest tasks are already complete, so now we can merge upwards: one-card parts become ordered two-card parts, and larger ordered parts follow. Reusing the same task on a smaller input is called recursion; here each smaller input has a visible place in the process.

The auxiliary row holds copies while the original two parts remain available to read. Once a merge is complete, copy its result back. This is why the display temporarily contains copies of a card; it does not mean the final list gains extra items. This implementation uses additional storage, and counts writes both into that storage and back into the main row.

06Quicksort: put a dividing card into its final position

Choose one card as a pivot: a value we use to divide the others. In this demonstration we choose the last card. Sweep through the other cards and collect values smaller than the pivot at the left. Keep a boundary after that smaller group. When a smaller value appears, exchange it into the boundary position and move the boundary one place right.

After the sweep, put the pivot at the boundary. Every value left of it is smaller; every value right of it is at least as large. The pivot therefore has a valid final position. The two sides may still be unordered, but they can now be sorted independently with the same procedure. Each recursive task excludes its pivot, so it gets smaller and eventually ends.

The strip below the cards shows the three groups during the sweep: already checked and smaller, already checked and not smaller, and not yet checked. The pivot waits separately at the end. Before each comparison the white boundary line ends the smaller group, and the arrow points to the next unchecked card. After the final card has been classified, no unchecked cards remain. You can go back a step to see exactly which group grew.

The name does not promise that every input is quick. Try the already ordered row. Choosing its last, largest value leaves an almost full left part and an empty right part. We have reduced the task by only one card. Different pivot strategies can avoid many such cases; they do not make this particular last-card demonstration immune to them.

07Count work, then ask what matters for this task

A value comparison asks which of two numbers is larger or whether they match. One array write stores an item in a position. Exchanging two different positions requires two array writes in these counters; assigning a temporary variable is not included. These counts explain what happened in this implementation. They are not seconds, and a comparison and a write need not cost the same time.

There is another requirement that the height of a bar cannot show. Suppose equal values stand for people with equal scores, already listed by arrival time. We may want to preserve that arrival order. A sorting method is stable if it preserves the original relative order of items with equal values. Follow the letters on equal cards. Bubble and this insertion method move cards only by exchanging neighbours. For two equal cards to reverse order, they would have to pass each other, which would require exchanging those two neighbours at some step. Our rule never exchanges equals, so that reversal cannot happen. Selection and our quicksort can instead move a card across several others in one exchange; they can cross an equal card without directly comparing that equal pair.

For merge sort, start with one-card parts, where no equal pair can be reversed. Assume the two smaller parts have kept their original equal-card order. Taking only each part’s front card keeps that order within the part. For equal cards from different parts, the left part originally came before the right part, so taking a left equal first keeps their order too. Each merge therefore preserves the property, all the way up to the complete row.

The quicksort procedure still needs a record of unfinished recursive tasks, even though it has no merge-style auxiliary row. Choosing a method therefore involves the data, required stability and storage, as well as comparison counts. To put the ordering to use, continue to the search lesson.

08Check whether you can explain the next move