Choosing the right sort
No single sorting algorithm wins everywhere — the right choice depends on data size, distribution, memory limits and whether you need stability. This reference puts the common algorithms side by side with their best, average and worst-case time complexity, space cost and stability, so you can pick deliberately. Search by keyword or sort the table by any complexity column.
How it works
Algorithms split into comparison sorts and non-comparison sorts:
Comparison sorts (≥ O(n log n) worst case):
Quick avg O(n log n), worst O(n²), in-place, unstable
Merge O(n log n) always, stable, needs O(n) extra space
Heap O(n log n) always, in-place O(1), unstable
Timsort O(n) best, O(n log n) avg, stable (Python/Java default)
Non-comparison sorts (linear, bounded keys):
Counting O(n + k) Radix O(d(n + k)) Bucket O(n + k) avgComparison sorts have a proven O(n log n) lower bound because they must distinguish all n! orderings. Non-comparison sorts beat it by exploiting integer key structure, trading memory and generality for speed.
Choosing by scenario
The table below maps common real-world needs to the algorithm that fits best:
| Scenario | Recommended algorithm | Reason |
|---|---|---|
| General arrays, unknown distribution | Quicksort (randomised) | Cache-friendly, O(n log n) average |
| Need worst-case O(n log n) | Mergesort or Heapsort | No O(n²) risk |
| Preserving equal-element order | Mergesort, Timsort, Insertion sort | Stable sorts only |
| Nearly-sorted input | Timsort or Insertion sort | Detects existing runs, approaches O(n) |
| Large arrays in tight memory | Heapsort | O(1) extra space |
| Integer keys in a bounded range | Counting sort or Radix sort | Linear time |
| External (disk-based) sort | Merge-based passes | Sequential I/O is cheap; random access is not |
Common mistakes to avoid
Using an unstable sort when ordering matters. If you first sort a list of transactions by amount and then by date using quicksort, the amount order is destroyed. Switch to mergesort, Timsort, or a stable variant.
Ignoring worst-case inputs. Naïve quicksort on an already-sorted array hits its O(n²) worst case. Always randomise the pivot or use median-of-three.
Picking a non-comparison sort for general objects. Radix and counting sort need integer (or fixed-width string) keys and extra memory proportional to the key range. They are not a drop-in replacement for comparison sorts on arbitrary data types.
Worked comparison
Sorting 1 million random integers as a reference point:
- Quicksort typically finishes first because it accesses memory sequentially in the inner loop (cache-friendly).
- Heapsort takes about 2–3× longer despite the same O(n log n) bound — heap-shaped access patterns thrash the cache.
- Mergesort sits in the middle but allocates O(n) extra memory, which can matter in memory-constrained environments.
- Timsort (Python’s built-in) would win if the array had any partially sorted structure, because it detects and merges natural runs.
Tips
- For general-purpose array sorting, a tuned quicksort (randomised or median-of- three pivot) is usually fastest; standard libraries often use Timsort or introsort under the hood.
- Need stability or worst-case guarantees? Use mergesort or Timsort.
- Sorting nearly-sorted data? Insertion sort and Timsort approach O(n).
- Tight on memory with a worst-case guarantee required? Heapsort sorts in place in O(1) extra space, at the cost of cache locality and stability.
- Use this reference’s sort-by-column feature to rank algorithms by worst-case space if your constraint is memory, or by best-case if your input is likely already ordered.