Seven algorithms sort the same input simultaneously. Each advances one logical comparison or movement per tick, so an earlier finish means fewer counted steps, not necessarily less wall-clock CPU time. Different inputs can change the ranking.
A race between seven sorting algorithms on the same array
Nearly sorted favors insertion sort and bubble sort, while reversed input makes both do much more work. Merge sort and heap sort are less sensitive to input order. Click an algorithm name in the table for its detailed simulation.
Complexity overview
| Algorithm | Best case | Average | Worst case | Extra space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Select | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes |
k is the range of values for counting sort. A stable sort preserves the order of equal values. Stability matters when applying successive sorting criteria, such as sorting by name and then by score.
Which algorithm should you use?
Python's sort() is stable and has O(n log n) worst-case time. Prefer a well-tested built-in implementation for ordinary sorting tasks.
Use merge sort when stability matters and extra memory is available, or heap sort when constant extra array space is important.
Insertion sort works well here. Many general-purpose implementations use insertion sorting for small subranges.
Counting sort takes O(n + k) without value comparisons. If only frequencies are needed, it can also reduce storage.
Coding exercises: choosing a sort key
Most tasks ask how to choose a key, rather than how to implement sorting. Tuple keys compare fields in order; negating a numeric field requests descending order for that field.
a.sort() # stable, in-place
b = sorted(a, reverse=True) # new list, descending
people.sort(key=lambda p: (-p[1], p[0])) # score descending, name ascendingAs a rough guide, quadratic algorithms may be viable for a few thousand items but become expensive around 100,000. Actual limits depend on language, hardware, and per-step work; measure rather than relying on a fixed one-second rule.