Comparing sorts.

Step 1 of 5

Four ways

One problem can have many algorithms. Algorithm offers four:

• Bubble compares neighbours and swaps, pass after pass.
• Insertion takes each block in turn and slides it left, swap after swap, until it meets a shorter block. So the left part of the row is always sorted, and grows by one block at a time.
• Merge splits the row into halves, and the halves into halves, down to single blocks, then merges pairs of sorted pieces: each comparison between the two front blocks lowers the shorter of them to the bottom shelf.
• Quick picks a pivot, here the last block, puts every shorter block to its left and every taller one to its right, and sorts each side the same way.

All of them end with the same sorted row. What sets them apart is how much work it takes. The row is now Nearly sorted: only a few blocks are a place or two out.

Step 2 of 5

Merge sort

Merge sort works in levels. Eight blocks split into two halves of four, four pieces of two and eight singles: $\log_2 8 = 3$⁠ levels. Then it merges back up, level by level. Merging two sorted pieces is quick, since it only takes comparing the two blocks at the front of each piece.

Merge sort’s plaque counts moves instead of swaps: each block goes down to the bottom shelf and back up, once per level.

Step 3 of 5

Swaps and inverted pairs

Bubble sort and insertion sort swap only neighbours. On this shuffled row bubble sort makes 120 comparisons and 72 swaps.

Step 4 of 5

The worst case

Quicksort is quick when the pivot lands in the middle, because then each partition halves the work, as in merge sort. But nothing guarantees it lands in the middle. An algorithm’s worst case is the input that makes it work hardest.

Step 5 of 5

Choosing a method

Now thirty-two blocks, Shuffled. Measure each of the four algorithms on the same row.