Sorting algorithms compared
Eight sorting algorithms side by side: time, space, stability, in-place or not, and, most importantly, when to reach for which.
| Algorithm | Time | Space | Best | Worst | Stable | In place | Difficulty |
|---|---|---|---|---|---|---|---|
| Bubble SortBubble sort | O(n²) | O(1) | O(n) | O(n²) | ✓ | ✓ | Intro |
| Selection SortSelection sort | O(n²) | O(1) | O(n²) | O(n²) | ✗ | ✓ | Intro |
| Insertion SortInsertion sort | O(n²) | O(1) | O(n) | O(n²) | ✓ | ✓ | Intro |
| Merge SortMerge sort | O(n log n) | O(n) | O(n log n) | O(n log n) | ✓ | ✗ | Intermediate |
| Quick SortQuicksort | O(n log n) average | O(log n) | O(n log n) | O(n²) | ✗ | ✓ | Intermediate |
| Heap SortHeapsort | O(n log n) | O(1) | O(n log n) | O(n log n) | ✗ | ✓ | Intermediate |
| Counting SortCounting sort | O(n+k) | O(n+k) | O(n+k) | O(n+k) | ✓ | ✗ | Intermediate |
| Radix / Bucket SortRadix and bucket sort | O(d·n) | O(n+k) | O(d·n) | O(d·n) | ✓ | ✗ | Intermediate |
When to pick which
Teaching, a few dozen items, or counting inversions on the side. Almost never in production.
When writes are expensive (EEPROM, flash): at most n−1 swaps, the fewest of any sort.
Nearly sorted or tiny input (n < 16). Quicksort and Timsort hand their small runs to it.
You need stability, a worst-case guarantee, external sorting of data that does not fit in memory, or a linked list.
The general-purpose default: smallest constants, cache friendly. Randomise the pivot to dodge the worst case.
You need the O(n log n) guarantee with no extra memory (embedded, real-time). Two to three times slower than quicksort in practice.
Keys are integers in a small range (scores 0–100, characters, ages). Wins whenever k is smaller than n log n.
Fixed-width integers or strings (phone numbers, IDs, dates); beats O(n log n) once n is large.
Choosing guide
- No idea: the language's built-in sort. It is usually Timsort (Python, Java objects) or introsort (C++), which already blend merge, insertion and heap for you.
- Ties must keep their order: the stable ones — merge, insertion, counting, radix. Quick and heap sort are not stable.
- Keys are small integers: counting or radix sort, the only way past the n log n lower bound, because they never compare.
- Nearly sorted: insertion sort in O(n). Bubble sort with early exit works too, but degrades when a small value sits at the end.
- Memory is tight: heap sort (O(1) extra, guaranteed n log n) or quicksort (O(log n) stack). Merge sort needs a second O(n) buffer.
- Data does not fit in memory: merge sort — read a chunk, sort it, write it out, then k-way merge the runs.