Spark & Anvil Privacy
A cozy library with green armchairs and shelves, two tweens sorting a row of books by height into order

📊

SortTales

Five ways to sort a list — and a surprise: the fastest one depends on the list.

🔮 Open the sorting console →

Six bars. Sort them.

Bubble walks the line checking each pair of neighbours, swaps any pair that is the wrong way round, and stops as soon as a whole walk swaps nothing.

Loading the bars…

What "fast" really means for a sorter

Every sorting algorithm does one basic move over and over: it compares two items and decides which comes first. The number of comparisons it makes is how much work it does — and here is the surprise: the same sorter does more or less work depending on the list. A simple sorter can beat a clever one when the list is already almost tidy. That feeling — how work grows with the list — is what computer scientists call Big-O.

  1. Predict. How many comparisons will this sorter make? Or which sorter is fastest here?
  2. Run. The bars move and a counter ticks up once for every comparison.
  3. Reveal. The real counts appear — you see for yourself which sorter won, and why.
  4. Race them. Run the same sorter on a tidy, a reversed, and a random list, and watch the count change.

Everything runs on your device — no internet, no accounts. These are real (tiny) sorting algorithms, the exact kind inside every program that puts things in order.

Meet the crew — the five sorters

  • Bubbly runs Bubble sort — compares each pair of neighbours and swaps the ones out of order, bubbling the biggest to the end. Fast when the list is nearly tidy; slow when it is a mess.
  • Inserta runs Insertion sort — builds the sorted list one item at a time, slipping each new item into its place. Great on almost-sorted lists.
  • Scanna runs Selection sort — scans the whole rest of the list every time to pick the smallest. She never notices the list is already sorted — she always does the same amount of work.
  • Quicka runs Quick sort — picks a pivot and splits the list into "smaller" and "bigger", then repeats on each half. Usually quick — hence the name.
  • Merga runs Merge sort — keeps splitting the list in half until each piece is one item, then merges the pieces back in order. Stays fast even on big, messy lists.
Where this idea comes from

Bubble sort

Sorting by machine is older than computers. In 1890 Herman Hollerith’s punched-card machines counted the United States census: each person was a card, and as a card was read, a lid opened on a sorting box to show which pile it belonged in. That was a different kind of sorting — dropping cards into piles, not swapping neighbours.

One thing to hold: Six cards with numbers on them, laid in a row. Swap any two neighbours that are the wrong way round, walk the row again, and count every pair you check.

Why it matters: In 1956 Edward Friend wrote about sorting by swapping neighbours. By the 1960s it was called bubble sort, because big values rise to the end like bubbles. Donald Knuth, in the 1998 edition of his great book on sorting, wrote that it “seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.”

What we don’t know: Nobody is sure who first called it bubble sort. Kenneth Iverson used the name in 1962, but in 1963 the Algorithms section of the journal Communications of the ACM printed the same idea as “Shuttle Sort”. People still argue about whether it should be taught at all.

Dates:

  1. 1890 Hollerith’s machines count and sort the US census cards.
  2. 1956 Friend writes about sorting by exchanging neighbours.
  3. 1962 The name bubble sort is in print.
  4. 1981 Sorting Out Sorting races sorting methods on film.
  5. 1998 Knuth’s verdict: nothing to recommend it but a catchy name.

Sources: Donald E. Knuth, The Art of Computer Programming, vol. 3: Sorting and Searching, 2nd ed. (1998), §5.2.2 · Owen Astrachan, “Bubble Sort: An Archaeological Algorithmic Analysis”, SIGCSE Bulletin 35(1), 2003 · Ronald Baecker, Sorting Out Sorting (film, University of Toronto, 1981) · Wikipedia, “Bubble sort” and “Tabulating machine”

What next? Pick a door

Chosen from what this app is about. What you open is remembered on this device only.