The Lab · von Neumann, 1945 · Hoare, 1959

Sorting Race

Every racer gets the same shuffled list. Each one takes one step at a time: one comparison, or one move. Who finishes first?

Who races

Tap to add or remove a racer. Changing anything restarts the race.

The list

Number of items50

The race

Speed4 steps a frame

Listen (a note for each step, pitched by the item's size)

Each bar is coloured by its size, smallest red to biggest violet, so a sorted list is a rainbow. being compared just moved

A swap moves two items and a write moves one, but each counts as one step. Every racer gets the same number of steps per frame, so the race shows the work done.

Results

n is the number of items. n² is n times n. log n is roughly how many times you can halve n before you reach 1: about 6 for 50 items, about 20 for a million.

Why it matters

Sorting is everywhere. Your contacts, your playlist, search results, the leaderboard in a game: something sorted them, often millions of times a day.

For a few items, any method will do. For a million, the gap is huge. n² is a million million steps. n log n is about twenty million. At a hundred million steps a second, that is nearly three hours against a fifth of a second.

And here is a deep fact: any method that only compares two items at a time needs about n log n comparisons in the worst case. No cleverness can beat it. Radix sort gets round this by never comparing at all.