How do computers sort large lists?

1. The library books are in a jumble. Bip the robot has to put them in order, from shortest to tallest. You could do it in a glance. But how does a computer do it?
2. A computer can only compare two things at a time. Bip looks at two books. If the taller one is on the left, they swap places. Every sort is built from this one small step.
3. One plan is bubble sort. Walk along the shelf comparing neighbors and swapping them when they are the wrong way round. Then do it all again, and again, until nothing needs swapping.
4. Here is a cleverer plan. Split the shelf in half, then split each half again, until every pile is a single book. A pile of one book is already in order!
5. Now merge the piles. To join two sorted piles, Bip only compares their front books and takes the shorter one. Pairs become fours, and fours become the whole sorted shelf.
6. For 8 books the two plans are close. For a thousand books, bubble sort needs about half a million looks, and merge sort about ten thousand. A good plan beats a fast computer.

Step through merge sort and watch eight books fall into order.

• A jumbled shelf. We start with eight books in no order at all. The goal is shortest on the left and tallest on the right.
• Split into single books. Split the shelf in half, then in half again, and once more. Now there are eight piles of one book. A pile of one is already sorted.
• Merge into pairs. Join the single books into pairs, shorter one first. That takes one look for each pair: four looks.
• Merge into fours. Merge two sorted pairs into a sorted four. Compare only the front book of each pair and take the shorter one. Each merge needs at most three looks.
• Merge the two halves. Merge the two sorted fours in the same way: front books only. At most seven looks later, the whole shelf is sorted.
• Count the looks. Add it up: 4, then at most 6, then at most 7 looks. That is 17 at most. Swapping neighbors can need 28 for the same shelf.

Choose a strategy and watch it sort the same jumbled shelf. Count the looks. Then try 16 books.

Experiment: Which strategy needs the fewest looks to sort 16 jumbled books?

1. Choose Bubble and read the number of looks.
2. Choose Merge and compare. Press Record after each run.
3. Switch to 16 books and run both again.

What we found: Merge sort needs the fewest looks, and the gap grows with the shelf. With 16 books, bubble sort and selection sort need more than a hundred looks, and merge sort fewer than fifty. Splitting the shelf means most books are never compared with each other at all.

Turn on JavaScript to try it yourself.

Five parcels look the same but weigh differently. Tap two to weigh them: the lighter one moves left. Get them in order, lightest first. For 3 stars, use 9 weighings or fewer.

Computers sort things all the time: names in a contact list, songs by title, search results from best to worst. But a computer cannot look at a whole list and just see the order, as you can with a few books. It can only compare two items at a time and decide which should come first.

So it needs a plan, a list of exact steps called an algorithm. The simplest plan is bubble sort: compare each pair of neighbors, swap them if they are the wrong way round, and repeat until nothing needs swapping. It always works, but it compares the same items over and over.

A cleverer plan is merge sort. Split the list in half again and again until every piece has one item. Then merge the pieces back together. Merging two sorted piles is quick, because you only need to compare the items at the front of each pile.

For a handful of items the plans are about the same. For a thousand, bubble sort needs about half a million looks and merge sort about ten thousand. It is like lining up for a class photo: groups that sort themselves and then join up beat everyone swapping with a neighbor. People can help by seeing several heights at once, though. A computer never can.

Key words

Algorithm

An exact list of steps for doing a job, such as putting a list in order.

Comparison

One look at two items to decide which should come first.

Bubble sort

Sorting by swapping neighbors that are the wrong way round, again and again.

Merge sort

Sorting by splitting the list into tiny pieces and merging them back in order.

Divide and conquer

Solving a big job by splitting it into smaller jobs that are easy.

n log n

A way of saying that the work grows only a little faster than the list does.

Check your thinking

1. What is the one small step that every sorting plan is built from?

   Show the answer

   Comparing two items and deciding which comes first. A computer cannot see the whole list. It can only compare two items at a time.

2. In bubble sort, what happens when a taller book stands to the left of a shorter neighbor?

   Show the answer

   The two books swap places. Neighbors that are the wrong way round swap. After enough passes, every book has moved to its place.

3. Why is merging two sorted piles so quick?

   Show the answer

   You only need to compare the front book of each pile. In a sorted pile the shortest book is at the front, so the next book for the shelf must be one of the two front books.

4. A shelf of 1,000 books must be sorted. Which plan will finish with far fewer looks?

   Show the answer

   Merge sort: split and merge. Bubble sort needs about half a million looks for 1,000 books. Merge sort needs about ten thousand.

5. Merge sort is much faster than bubble sort on large lists. What does it pay for that speed?

   Show the answer

   Extra memory to hold the piles while they are merged. Merging copies items into spare space, about as much again as the list. The result is exactly right, and any length works.