Interactive
The sorting lab
Ordering is slower than it looks. The same set of bars can be put in order by several common methods, and each one spends its effort differently. The lab lets you watch that difference, one comparison at a time.
We use the lab as a way of thinking about editorial sequence. Every step has a cost, and some methods waste more of it than others. A document that makes its reader check every page to find one answer wastes the reader in the same way.
Live sorter
Watch one comparison at a time
The sorter runs entirely in your browser. Nothing is saved or sent anywhere.
The live controls need JavaScript. Without it, the snapshots below show the kind of run they would make.
Pick a method and a number of bars. Step forward to take one action at a time, or play the run at the speed you choose.
Reduced motion is on, so playback is turned off. Use step forward to move one action at a time, or finish to see the final order.
Step 0 of 0 · Comparisons 0 · Moves 0
- Starting order
- After one pass
- Sorted
The methods
Four common ways to reach the same order
Bubble sort
Bubble sort walks along the list, comparing each pair of neighbors and swapping any pair that is out of order. Each full pass carries the largest remaining value to the end, like a bubble rising. It is the easiest method to explain and the slowest on long lists, because it keeps checking pairs that are already in the right place.
Insertion sort
Insertion sort takes one item at a time and slides it left into the part of the list that is already in order, the way a card is placed into a hand that has been sorted. It is quick on a list that is nearly in order and slow on one that is badly scrambled, because each item may have to travel a long way.
Selection sort
Selection sort scans the unsorted part for the smallest value and moves it to the front. It makes very few moves, but it still scans everything that remains each time, even when the list is already in order. It suits situations where moving items is expensive and checking them is cheap.
Merge sort
Merge sort divides the list into halves, sorts each half and then merges the two sorted halves into one. On long lists it does far less comparison work than the first three methods, and it belongs to the family behind many everyday sorting routines. Its cost is the extra room the merge needs.
Reading the counts
What the numbers on the sorter mean
Comparisons count how often two bars are checked against each other. Moves count changes to the arrangement: swaps for bubble, insertion and selection sorts, and writes back into the list for merge sort.
Use the counts to compare methods on the same starting order. They describe the work each method asks for on that particular set of bars. They are not a measure of how fast a browser or a computer will run it.
For the ideas behind these methods, and for the questions to ask before anything is rearranged, read the short guide to putting things in order.