ApliantSame input, same clock
Every lane gets the same values in the same order. On each tick of the clock every algorithm may do one step. Who finishes first? Change the clock to comparisons and only comparisons cost time: the algorithms that never compare finish at once.
Leaderboard
A "step" is one comparison, swap, write or read. Real computers do not spend the same time on each, but counting steps is how algorithms are compared on paper.
How does the cost grow with n?
Each algorithm runs for real, without animation, for n = 8, 16, 32 … 4096 and we count its work. On a log-log chart a power law is a straight line: the steeper the line, the faster the cost explodes. Dashed: the reference curves n², n log₂ n and log₂(n!), the least any comparison sort must do.
Log-log scales. Hover the chart to read the values. Quadratic algorithms stop at n = 1024 (they get slow).
Measured at the largest n
Click a row to show or hide its line. Growth is the slope of the last part of the line: about 1 means n log n (a bit above 1), 2 means n².
What to look for
On random input the lines split into two families: the quadratic ones, parallel to n², and the n log n ones, close to the lower bound. Doubling n makes the first family 4 times slower and the second only a bit more than 2 times.
Now try sorted input. Insertion sort and bubble sort drop to about n comparisons: they notice that nothing has to move. Quicksort with the last element as pivot does the opposite and becomes quadratic, because every pivot is the largest value. The median of 3 fixes that. On few unique values the Lomuto quicksort suffers again: values equal to the pivot all go to the same side.
Switch to array writes: selection sort, the slowest in comparisons, writes the least. Binary insertion sort does the opposite: few comparisons, many writes. Which cost matters depends on the machine.
The number next to each line counts how many times it has run. That is where the time goes.
Variables
Last steps
Why sort at all? To find things fast
Looking for a value in a list. Linear search checks one value after the other: up to n checks. If the list is sorted, binary search looks at the middle and throws away the half where the value cannot be. Each check halves what is left, so it needs at most about log₂ n checks. Click a bar to choose what to look for.
Guess the number (1 to 1000)
How many questions?
Each yes/no answer halves the possibilities. With k questions you can tell apart 2k numbers, so for n numbers you need log₂ n questions, rounded up. 210 = 1024, which is why 10 guesses always reach any number up to 1000.
This is the same halving that makes merge sort and quicksort fast: log₂ n levels of splitting, each costing about n.
Equal values: who goes first?
These cards are sorted by their number only. Cards with the same number are "equal", but they are not the same card. A stable sort keeps equal cards in the order they had before. Pink outlines show the cards that changed order. Shuffle a few times: an unstable algorithm can keep the order by luck, but not always.
The same hand, sorted by each algorithm
Why it matters: sorting by two keys
You want the cards by number, and cards with the same number by suit (♠ ♥ ♦ ♣). Trick: sort by suit first, then by number with a stable sort. The second sort keeps the suit order among equal numbers. Spreadsheets do this when you sort by one column and then by another.
Properties
In place: needs only a few extra variables, not another array. Extra memory is counted in cells, as in the Sort tab.
Sorting is a game of yes/no questions
A comparison sort learns about the input only by asking "is a smaller than b?". Write down every question it might ask and you get a decision tree. Each possible order of the input must end in its own leaf. There are n! orders, and a tree of depth d has at most 2d leaves, so the worst case needs at least log₂(n!) questions. No cleverness can beat that.
Each box is a question about the original values a, b, c, d. Each leaf is the sorted order found. Click a leaf to follow its input.
The bound for large n
By Stirling's formula, log₂(n!) ≈ n log₂ n − 1.44 n. Measured averages on random input (3 runs each) next to the bound. The best comparison sorts stay within a few percent of it.
Escaping the bound
The bound only covers algorithms that learn by comparing. Counting sort and radix sort never compare two values: they use the value itself as an address ("put every 7 in box 7"). That is why they can sort in about n + k steps.
The price: the keys must be small whole numbers, or be split into digits. Counting sort cannot follow a custom rule like "by distance to home". For general data, n log n is the best possible.
The bound is about the worst case, and the average can't do better either: the average depth of a tree with n! leaves is also at least log₂(n!). Insertion sort on almost sorted input is faster only because that input is not random.
What is an algorithm?
A recipe so precise that a machine can follow it without thinking. "Sort these numbers" is a wish. "Compare the first two; if they are out of order, swap them; move one step to the right; repeat" is an algorithm. Different recipes reach the same result with very different amounts of work.
Counting the work
Seconds depend on the computer, so we count basic steps instead: comparisons, swaps, writes. A comparison is the step every general sort needs, so it is the classic cost. This lab counts every single one: the numbers you see are exact, not estimates.
Big O: how the cost grows
We care less about the cost for 10 values than about how it grows. Bubble sort needs about n²/2 comparisons: 50 for 10 values, half a million for 1000, half a trillion for a million. Merge sort needs about n log₂ n: 33, about 10 thousand and 20 million. We write O(n²) and O(n log n) and ignore the constants.
Divide and conquer
Merge sort splits the array in two halves, sorts each one (the same way), and merges them. Splitting n values in halves takes log₂ n levels, and each level does about n steps of merging: n log₂ n in total. Quicksort splits differently: it picks a pivot and puts the smaller values on its left. Good pivots split in halves; bad ones split off a single value, and the cost becomes n².
Heaps: a tree hidden in an array
In a heap the children of position i are at 2i+1 and 2i+2, and every parent is larger than its children. So the maximum is always at position 0. Heapsort moves it to the end, repairs the heap with at most log₂ n swaps down the tree, and repeats: n log n, with no extra array.
Sorting without comparing
If the values are small whole numbers, count them: three 1s, zero 2s, five 3s… then write them back. That is counting sort. Radix sort does it digit by digit, starting with the last one. Machines did this with punched cards long before electronic computers: one pass per column, dropping each card into one of ten pockets.
Listening to an algorithm
Each step plays the value it touches as a pitch: low values low, high values high. A sorted array played from left to right is a rising glissando. Bubble sort sounds like a slowly climbing buzz, merge sort like many short rising runs that join, radix sort like the same melody coming back cleaner each pass. Your ears can tell the algorithms apart!
A short history
1890s: punched-card machines sort census data by radix. 1945: John von Neumann writes merge sort for the EDVAC, one of the first programs ever. 1959: Donald Shell publishes Shellsort, and Tony Hoare invents quicksort while studying in Moscow (published 1961). 1964: J. W. J. Williams invents heapsort. 1968: Ken Batcher designs the bitonic sorter for parallel hardware. Today's libraries mix ideas: Timsort (2002) is a merge sort that profits from runs already in order, and C++'s introsort is a quicksort that switches to heapsort when it goes badly.
Challenges
- Sort 64 random values with insertion sort and with the same input already sorted. How many comparisons in each case?
- Find an input order that makes quicksort (Lomuto) as slow as bubble sort. Check it in the Complexity tab.
- Which algorithm makes the fewest swaps on random input? Which one the most?
- Close your eyes, let someone pick an algorithm, and guess it by its sound.
- In the race, put merge sort against counting sort with the clock on comparisons. What happens, and why is it not cheating?
- Play the guessing game with the computer guessing. Can you make it need more than 10 questions without lying?
- In the Lower bound tab, find an algorithm that asks a question whose answer it already knew.
- Bogosort with 6 values: how many shuffles did it need? Try a few times and compare with 6! = 720.
About
Science in Motion is created and maintained by Eduardo Correia, sponsored by Apliant.
Shortcuts
space play / pause · → one step · ↑↓ faster / slower · +− more / fewer values · [] previous / next algorithm · N new input · R restart · V change the view · M sound on/off · S show mode · H hide/show the menu
In the Race tab space starts and pauses the race; in the Search tab it starts the search.