Time Complexity of Sorting Algorithms: The Big O Cheat Sheet
A complete Big O cheat sheet for sorting algorithms — best, average, and worst-case time complexity plus space complexity and stability for all 10 algorithms.
On this page +
If you only memorize one thing about sorting algorithms, make it the Big O table. Time complexity tells you how the running time grows as the input grows, and it is the single most common interview question about sorting. Here is the complete cheat sheet, plus the intuition for why each number is what it is.
The complete cheat sheet #
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Shell Sort | O(n log n) | O(n^1.25) | O(n²) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
What O(n log n) actually means #
O(n log n) means that for each of the n elements, roughly log n units of work are done. The practical impact is enormous: sorting 1,000,000 items takes about 20 million operations with an O(n log n) algorithm versus 1 trillion with an O(n²) one. That is the difference between milliseconds and minutes.
Why best, average, and worst differ #
The three columns matter because real inputs are not always random. Insertion Sort hits its O(n) best case on nearly-sorted data but O(n²) on reversed data. Quick Sort averages O(n log n) but degrades to O(n²) if pivots are chosen badly. Merge and Heap Sort give the same O(n log n) regardless of input, which is why they are valued when worst-case guarantees matter.
See the difference live #
Numbers in a table are abstract. Run Bubble Sort and Merge Sort side by side in the visualizer on a 100-element array and watch how many more comparisons the O(n²) algorithm needs. The docs page also has a printable complexity reference.
Best, average and worst case #
A single Big-O figure hides something important: most sorting algorithms have three different complexities, depending on what the input looks like when it arrives.
- Best case — the most favourable possible input. For Insertion Sort that is an already-sorted array: one pass, nothing to shift, O(n).
- Average case — the expected cost across random input orders. This is usually the figure worth planning around.
- Worst case — the most hostile possible input. For Quick Sort with a naive first-element pivot, that is also an already-sorted array, which collapses it to O(n²).
Look at how often "already sorted" appears in both columns. The exact input that is Insertion Sort's best case is naive Quick Sort's worst case. Input order is not an implementation detail — it is part of the problem you are solving.
You can watch this collapse happen. In the visualiser, run Insertion Sort on a shuffled array and note the comparison counter. Let it finish, then press Sort again on the now-sorted array: the count drops from roughly n²/4 to n−1. That is the gap between average and best case, measured rather than asserted.
Frequently asked questions
Which sorting algorithm has the best time complexity? +
What is the worst-case time complexity of Quick Sort? +
Why is O(n log n) considered optimal for sorting? +
Which case matters most in practice? +
Why is Quick Sort used everywhere if its worst case is O(n²)? +
See it in motion
Watch this algorithm and nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.