Time Complexity of Sorting Algorithms: The Big O Cheat Sheet
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.
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? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser