Comparison of Sorting Algorithms: Time, Space & Stability
Choosing a sort comes down to four questions: How big is the data? Is it nearly sorted? Do you need a worst-case guarantee? Do you need stability or low memory? This page puts every algorithm from this section side by side so you can answer those questions at a glance, then gives concrete guidance.
The master comparison table
n is the number of elements; k is the value range (counting sort); d is the number of digits (radix sort).
| Algorithm | Best | Average | Worst | Space | Stable | Comparison? |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | No |
| Radix sort | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | Yes | No |
Note on quick sort’s space:
O(log n)is the average recursion-stack depth; a naive implementation isO(n)in the worst case. Quick sort uses no extra array, which is its memory advantage over merge sort.
Key takeaways from the table
- The O(n²) sorts (bubble, selection, insertion) are simple and in-place but only viable for small or nearly-sorted inputs. Among them, insertion sort wins for nearly-sorted data; selection sort wins when writes are costly.
- The O(n log n) comparison sorts are the general-purpose workhorses. Merge is stable with a worst-case guarantee but costs
O(n)memory; quick is fastest in practice but unstable with anO(n²)worst case; heap guaranteesO(n log n)inO(1)space but is cache-unfriendly. - The linear-time sorts (counting, radix) beat
O(n log n)but only for integer-like keys in a bounded range.
For beginners: No comparison sort can do better than
O(n log n)in the worst case — that’s a proven lower bound. Counting and radix sort are faster only because they don’t compare elements; they read the keys directly, which needs special data.
Which sort should I use?
A practical decision guide:
- In real code, call the built-in sort. Library sorts are battle-tested hybrids (introsort, Timsort) that beat anything you’ll hand-write. Only implement your own to learn, or for a special structure.
- Need stability (preserve order of equal keys, e.g. multi-key sorting)? Use merge sort / Timsort. Python’s
sortedand Java’s objectArrays.sortalready are stable. - Memory-constrained and need a worst-case guarantee? Heap sort —
O(n log n),O(1)space. - Fastest average, stability not needed? Quick sort with a randomized pivot.
- Small array (≤ ~16) or nearly sorted? Insertion sort.
- Integer keys in a small range? Counting sort. Larger fixed-width integers? Radix sort.
- Linked list? Merge sort — it merges sequentially and needs no random access.
What the standard libraries actually do
- C++
std::sort— introsort: quick sort, falling back to heap sort on deep recursion and insertion sort on tiny ranges. Not stable.std::stable_sortis a merge sort. - Java
Arrays.sort— dual-pivot quick sort for primitives (not stable); Timsort (merge + insertion) for objects (stable). - JavaScript
Array.prototype.sort— required to be stable since ES2019; engines use Timsort-like algorithms. - Python
sorted/list.sort— Timsort, stable.
See exact usage and the comparator pitfalls on the built-in sorting page. Ready to practice? Head to the sorting exercises.