A row of blocks and one question
Put a row of blocks in order of height. With eight blocks you just look, but a computer cannot see the whole row at once. All it can do is pick up two blocks, ask which is taller, and move them. A method for doing that is an algorithm: a list of steps precise enough for a machine to follow without thinking.
Every sorting algorithm in the Scene is built from the same move. When two blocks rise under a bracket they are being compared. A blue bracket means they are already in order; an orange one means they swap. The brass plaque counts every comparison, and since comparing is the work every method has to do, that count is the fairest way to say how much work a method did.
Four ways to sort
Bubble sort walks along the row comparing neighbours and swapping any pair that is out of order. After one pass the tallest block has bubbled to the end; after the next, the second tallest; and so on. If a pass makes no swaps the row is sorted and it stops.
Insertion sort works like sorting a hand of cards. It takes the blocks one at a time and slides each one left past every taller block until it meets a shorter one. The left part of the row is always sorted.
Merge sort splits the row in half, sorts each half, and merges the two sorted halves by repeatedly taking the shorter of their two front blocks. The halves are sorted the same way, down to single blocks, which are sorted already. In the Scene each merge builds its result on the lower shelf, then lifts it back.
Quicksort picks one block as the pivot, here the last block of the stretch it is sorting, marked with a small orange pin. It moves every shorter block to the left of the pivot and every taller one to the right, which puts the pivot in its final place. Then it sorts the two sides the same way.
Try it: choose Bubble and slide List size up to 64 blocks, then switch the Algorithm to Merge. The same 64 blocks take bubble sort about 2,000 comparisons and merge sort about 300.
Counting the comparisons
Bubble sort on a reversed row has to compare every block with every other one. With n blocks there are n(n − 1)/2 pairs: 28 for 8 blocks, 2,016 for 64. Double the row and the work roughly quadruples. Insertion sort does about half that on a shuffled row, but it grows the same way. Computer scientists write this growth as O(n²), read “order n squared”.
Merge sort does less work because every comparison in a merge settles one block’s place in the merged run for good. The row can only be halved about log₂n times (6 times for 64 blocks), and each round of merging compares each block at most once, so the total is at most about n × log₂n: 321 comparisons at most for 64 blocks. Quicksort on a shuffled row averages a little more, about 360 comparisons for 64 blocks. This is O(n log n) growth, and no method that works only by comparing pairs can beat it, even on average.
Choose Growth under Show how it grows to see the two curves side by side. The orange ribbon is n(n − 1)/2, the blue one n log₂n. The white curve is the chosen algorithm’s count at every list size, averaged over 24 starting rows of the chosen kind, and the dot climbs as this run counts.
The starting row matters
The same algorithm can be fast or slow depending on the row it is given. On a Nearly sorted row, insertion sort barely moves anything: each block is compared once or twice and stays put, so the count is close to n. That is why insertion sort is still used for small or almost-ordered lists.
The quicksort here is the opposite. Choosing the last block as the pivot works well on a shuffled row, but on a sorted or Reversed row the pivot is always the tallest or shortest block left. Every split then puts nothing on one side, and the count climbs to n(n − 1)/2, as bad as bubble sort. Real libraries pick the pivot from the middle, from a sample, or at random, and some switch to another method when the splits go wrong.
What this model leaves out
The counts are exact for these four programs, and each of them could be written a little differently: a bubble sort without the early stop, or a merge sort that skips merging halves already in order, would count differently. Comparisons are not the whole cost. Merge sort needs a second shelf as long as the row, while the others sort in place; swapping or copying takes time too, and on a real computer the order in which memory is touched can matter as much as the count. Real data also brings repeated values and records that must keep their original order, which these distinct blocks avoid. Finally, the Scene plays each list size at its own pace, faster for longer lists, so compare times on screen only at one list size.