Saramsha

No. 048  ·  3 November 2026

Bubble Sort Never Wins

Four sorting algorithms start from the same shuffled list and race to put it in order. Every comparison and every write plays a note, pitched to the value it touches. Press start and listen: two algorithms finish in a handful of notes, and two grind on long after.

About this piece

Same amount of work per second. Wildly different amounts of work.

All four lanes here run at the same rate: the speed slider sets how many comparisons and writes happen per second, and that rate is identical across all four. Nothing is given a head start. The only reason one lane crosses the line before another is that it needed to touch the list fewer times to finish — and that difference is almost entirely about the shape of each algorithm, not the list size slider, which affects all four equally.

Bubble sort walks the whole list, swapping any pair that's out of order, and repeats that full walk as many times as the list is long. Insertion sort builds up a sorted front section one item at a time, sliding each new item back through everything bigger than it. Both of these do roughly n² work for a list of n items — double the list and they do roughly four times the work, not twice.

Quicksort picks one item as a pivot, shuffles everything smaller to its left and everything bigger to its right in a single pass, then recurses on each side. Merge sort instead splits the list in half, sorts each half recursively, then merges the two sorted halves back together in one pass. Both keep halving the problem, so a list of n items only needs about log₂n rounds of halving, each round touching roughly n items — about n·log₂n work in total. Double the list and the work barely more than doubles. At n = 32 that is the difference between roughly 500 operations and roughly 160; at n = 1,000 it is 500,000 against 10,000.

What you're actually hearing

Every comparison or write plays a short note, pitched low for a small value and high for a large one, in a different timbre per lane so you can tell them apart when two notes land close together. A sparse, slow stream of distinct notes is quicksort or merge sort, each one doing real work toward a halving. A dense, almost continuous buzz is bubble or insertion sort, re-examining the same stretch of list for the fourth or fifth time. At high race speeds some notes are skipped so the audio doesn't turn into static, but every skipped note still happens and still counts in the tally on the right.

Bubble sort gets its name from the way large values rise to the top of the list one swap at a time, the way bubbles rise through water — and nearly every introductory algorithms course still teaches it, not because anyone should use it, but because its n² cost is the easiest one to prove by hand. Quicksort was published by Tony Hoare in 1961 and, despite that n² worst case lurking if the pivot keeps landing badly, remains one of the most-used sorts in practice because its average case on ordinary data is both fast and cache-friendly. Merge sort, older still, traces back to John von Neumann in 1945, and is the one most standard libraries fall back to when they need a guarantee that never degrades, worst case included.

This quicksort always picks the last element of each slice as its pivot (the classic Lomuto scheme), which has a well-known n² worst case on an already-sorted or reverse-sorted list — not visible here, since every race starts from a fresh random shuffle. ?warm= fast-forwards the race so a screenshot shows lanes mid-sort rather than an unshuffled start.