Sorting algorithms, animated and compared

Every sorting algorithm below takes a list of numbers and puts it in increasing order. They differ in how: which pairs they compare, how they move values, how much extra memory they need, and how their running time grows. The visualiser highlights the line of pseudocode being executed and explains each step in words. Change the input to see how the algorithms react to sorted, reversed and repetitive data.

The seven algorithms

Bubble sort

Bubble sort walks along the array swapping any neighbouring pair that is out of order. After the first pass the largest value has “bubbled” to the end; after the second, the two largest are in place; and so on. If a whole pass makes no swaps, the array is sorted and it can stop early, which is why its best case is linear. It is easy to understand and almost never the right choice: it makes $n(n-1)/2$ swaps on reversed input, one for every out-of-order pair.

Insertion sort

Insertion sort grows a sorted prefix. It lifts out the next value (the key), slides every larger value in the prefix one place to the right, and drops the key into the gap. On nearly sorted input each key moves only a little, so insertion sort is fast there, and it is the standard choice for short arrays inside bigger algorithms.

Selection sort

Selection sort scans the unsorted part for its minimum and swaps it to the front. It always makes exactly $n(n-1)/2$ comparisons, whatever the input, but never more than $n - 1$ swaps. That makes it a reasonable choice only when writing to memory is much more expensive than reading.

Merge sort

Merge sort is divide and conquer: split the array in half, sort each half recursively, and merge the two sorted halves by repeatedly taking the smaller front element. Merging $n$ elements costs at most $n - 1$ comparisons, and the halving gives $\log_2 n$ levels, so the total is $O(n \log n)$ on every input. The price is a buffer of size $n$. Merge sort is stable, and its sequential access pattern suits linked lists and data on disk.

Quicksort

Quicksort, published by Tony Hoare in 1962, also divides and conquers, but does the work before recursing. It picks a pivot and partitions the array so that smaller values come before it and the rest after; the pivot is then in its final place, and the two sides are sorted independently. The visualiser uses the simple Lomuto partition with the last element as pivot.

When pivots split the array roughly in half, quicksort takes $O(n \log n)$ time and, in practice, is usually the fastest of the comparison sorts because its inner loop is tight and cache-friendly. When pivots are consistently the smallest or largest value, each partition removes only one element and it degrades to $O(n^2)$. With the last element as pivot that happens on input that is already sorted: try the “Reversed” button, then sort the sorted result again. Real implementations avoid this by choosing the pivot randomly or as the median of three samples.

Heapsort

Heapsort first rearranges the array into a max-heap, a binary tree stored in the array where $A[i]$ is at least as large as its children $A[2i+1]$ and $A[2i+2]$. The maximum is then at the root. It swaps the root to the end, shrinks the heap by one, and sifts the new root down to restore the heap property. It guarantees $O(n \log n)$ time with constant extra space, but jumps around memory, so it is usually slower than quicksort in practice.

Counting sort

Counting sort never compares two elements. It counts how many times each value occurs, then writes the values back in order. For $n$ integers between 0 and $m$ it takes $O(n + m)$ time, so it beats every comparison sort when the range is small. It is the building block of radix sort, which sorts numbers digit by digit.

Stability

A sort is stable if elements that compare equal keep their original order. That matters when you sort records by one field after another. Sort a list of people by first name, then stably by surname, and people with the same surname end up in first-name order. Merge, insertion, bubble and counting sort are stable as written here; selection sort, quicksort and heapsort can move an element past an equal one.

Why $n \log n$ is the limit for comparison sorts

Any algorithm that learns about the order only by comparing pairs can be drawn as a binary decision tree: each internal node is a comparison, each leaf an output order. To sort correctly it needs a different leaf for each of the $n!$ possible orderings of the input. A binary tree with $n!$ leaves has height at least $\log_2 n!$, so some input forces at least that many comparisons, and

For 12 elements, $12! = 479{,}001{,}600$ and $\log_2 12! \approx 28.8$, so every comparison sort needs at least 29 comparisons on its worst 12-element input. Open the comparison table under the visualiser with the input 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 to see where each algorithm lands. Counting sort escapes the bound because it is not a comparison sort: it uses the values themselves as array indices.

What real libraries use

Production sorts are hybrids that combine the strengths above.

• Timsort (Tim Peters, 2002) finds runs that are already in order, extends short ones with insertion sort, and merges them. It is stable and very fast on partly sorted data. Python’s list.sort, Java’s sort for object arrays, and V8’s Array.prototype.sort (used in Chrome and Node.js) are Timsort or descendants of it.
• Introsort starts as quicksort, switches to heapsort if the recursion gets suspiciously deep, and finishes small ranges with insertion sort, which guarantees $O(n \log n)$. It is the usual implementation of C++’s std::sort.
• Dual-pivot quicksort partitions around two pivots at once; Java uses it for arrays of primitive values.

References

1. C. A. R. Hoare, “Quicksort”, The Computer Journal 5(1), 1962. doi:10.1093/comjnl/5.1.10
2. J. W. J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM 7(6), 1964.
3. D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
4. “Sorting algorithm”, Wikipedia.