Seven sorting algorithms on the input of your choice, one frame at a time. The counters underneath show exactly how many comparisons and writes each one spends, so the difference between them is a number rather than a claim.
Quick sort: pick a pivot, move everything smaller to its left, then recurse on each side.
Usually the fastest in practice thanks to cache behaviour, but the worst case is real without a good pivot.
| Algorithm | Comparisons | Writes | Worst case |
|---|---|---|---|
| Bubble sort | 117 | 114 | O(n²) |
| Selection sort | 120 | 26 | O(n²) |
| Insertion sort | 69 | 72 | O(n²) |
| Merge sort | 46 | 64 | O(n log n) |
| Quick sort | 42 | 46 | O(n²) |
| Heap sort | 85 | 112 | O(n log n) |
| Counting sort | 0 | 16 | O(n + k) |
Counting sort runs on a smaller value range than the others, since it needs one bucket per distinct value.
For general use, quick sort is usually fastest in practice because its inner loop is tight and cache-friendly, even though its worst case is O(n²). Merge sort matches it asymptotically and is stable but needs O(n) extra memory. Real language runtimes mostly use hybrids: Timsort in Python and Java for objects, and introsort (quick sort that falls back to heap sort) in C++.
A stable sort keeps equal elements in their original relative order. It matters whenever records are sorted by more than one field: sort by name, then stably by department, and within each department the names are still in order. Merge, insertion, bubble and counting sort are stable; quick, heap and selection sort are not.
A comparison sort learns about the input only through yes/no comparisons, so a run of c comparisons can distinguish at most 2^c different orderings. There are n! possible orderings, so 2^c must be at least n!, which gives c ≥ log2(n!) ≈ n log n. Counting and radix sort get around this by not comparing elements at all.
On small arrays and on nearly-sorted data, where it runs in close to linear time. That is why production sorts switch to insertion sort once a partition drops below roughly 10 to 30 elements: at that size its low overhead beats the recursion of an asymptotically better algorithm.
A comparison asks which of two elements is larger; a write stores a value into the array. They are counted separately because they can cost very different amounts. Selection sort does O(n²) comparisons but only n-1 swaps, which makes it attractive when writing is expensive, such as to flash memory.