Sorting Algorithms Big O Cheat Sheet

n = number of elements. k = the range of the key space (for Counting Sort) or the number of digits/passes (for Radix Sort).

• * Shell Sort's complexity depends entirely on its gap sequence. O(n log²n) is the figure for good sequences such as Ciura's; naive halving gaps are worse.
• † Quick Sort's O(n²) worst case requires an adversarial input and a poor pivot rule. With a randomised pivot it is vanishingly unlikely.
• ‡ Bucket Sort degrades to O(n²) when every element lands in the same bucket, i.e. when the data is not roughly uniformly distributed.

Before the table is useful, four ideas need to be concrete rather than notational.

Time complexity is a growth rate, not a duration. O(n²) does not mean "slow"; it means that if you double the input, the work roughly quadruples. O(n log n) means doubling the input barely more than doubles the work. For 20 items nobody can tell the difference. For 20 million, one finishes before you look up and the other does not finish today.

Best / average / worst describe the input, not the machine. Best case is the friendliest possible input (usually "already sorted"), worst case is the most hostile one (often "reverse sorted"), and average case is what you get from random data. This is why Insertion Sort has a spectacular O(n) best case and a mediocre O(n²) worst case — it is the same algorithm doing very different amounts of work depending on what you hand it.

Space means extra space. Every algorithm needs room for the array itself; the space column counts only the scratch space on top. O(1) means a couple of loop variables. O(n) means it allocates a second array as large as the first. See in-place vs out-of-place sorting for why that distinction matters more than it sounds.

Stable means equal items keep their original order. If two records tie on the key you are sorting by, a stable algorithm guarantees the one that was earlier stays earlier. This is not a nicety — it is what makes "sort by date, then sort by name" work as a two-step operation.

Numbers in a table are abstract, so here is a concrete scenario. Suppose you are building a leaderboard and you sort the player list on every page load.

With 500 players, Bubble Sort performs roughly 250,000 comparisons. That is genuinely nothing — well under a millisecond. Ship it, nobody notices.

Your game gets popular and the list reaches 50,000 players. Bubble Sort now performs roughly 2.5 billion comparisons per page load. Merge Sort, on the same list, performs roughly 780,000 — about three thousand times fewer. The code did not change, the input grew, and one algorithm quietly fell off a cliff while the other shrugged.

That ratio is the entire practical content of the table. O(n²) algorithms are fine at small scale and catastrophic at large scale; O(n log n) algorithms scale almost linearly for any input you will realistically meet. The reason interviewers care is not the notation — it is that this cliff is invisible in testing and obvious in production.

You do not need to memorise twelve rows. You need five rules, and the table falls out of them.

• Nested loops mean O(n²). Bubble, Selection and Insertion Sort all walk the array inside another walk of the array. Three algorithms, one reason.
• Halving the problem means a log factor. Merge Sort, Quick Sort and Heap Sort all repeatedly cut the work in half, which happens log n times, and each level costs O(n). Hence O(n log n).
• Only the adaptive ones get an O(n) best case. Bubble Sort (with the early-exit flag), Insertion Sort and Tim Sort can detect that the data is already ordered and stop. Selection Sort cannot — it always scans the whole remaining array — which is why its best case is still O(n²). See adaptive sorting.
• Extra memory buys stability. The stable algorithms are the ones that either shift rather than swap (Insertion, Bubble) or copy into scratch space (Merge, Tim, Counting, Radix). The unstable ones (Quick, Heap, Selection, Shell) all move elements over long distances to save memory.
• Only non-comparison sorts beat O(n log n). Counting, Radix and Bucket Sort escape the barrier because they use the key as an index instead of comparing pairs. Everything else is capped — see why O(n log n) is the lower bound.

Learn those five and you can rebuild the table on a whiteboard, which is the version of "knowing it" that survives being asked a follow-up question.

If you are short on time, four rows carry almost all the weight in interviews and in real code:

• Merge Sort — O(n log n) in every case, stable, needs O(n) space. The dependable one.
• Quick Sort — O(n log n) average and the fastest in practice, but unstable with an O(n²) worst case. The fast one.
• Heap Sort — O(n log n) guaranteed and O(1) space, but unstable and cache-unfriendly. The only algorithm that gives you both guarantees at once.
• Tim Sort — O(n) on nearly-sorted data, O(n log n) worst case, stable. What Python and Java actually run, which is why it is the answer to "what does the standard library use".

Then open the visualiser and watch the comparison counter while the same array is sorted by an O(n²) algorithm and an O(n log n) one. Seeing the counter for Bubble Sort race past Merge Sort's final total while the bars are still half-shuffled makes the table stop being trivia and start being intuition.