Sorting Algorithms Cheat Sheet: Time, Space, and When to Use Each
- Comparison sorts have a hard floor of Ω(n log n); counting, radix, and bucket sort escape it by never comparing elements
- Quicksort wins for general in-memory data: in-place, cache-friendly, and O(n log n) average with a randomized pivot
- Merge sort is right for linked lists, stable sorting needs, and any case requiring a guaranteed O(n log n) worst case
- Build-heap is O(n), not O(n log n); heap sort is the only comparison sort with both O(n log n) worst case and O(1) auxiliary space
- Python and JavaScript use TimSort; C++
std::sortuses introsort; Go and Rust's unstable sort use pdqsort - Interviewers rarely ask you to implement a sort; they ask you to choose one and explain the tradeoffs behind every row
You have fifteen minutes before the interview starts. You remember "pivot" and "O(n log n)" and not much else. Here's everything you actually need.
The Table You Came Here For
| 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 |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | Yes |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Yes* |
| TimSort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
*Bucket sort is stable only if each bucket uses a stable inner sort.
Quicksort's space is O(log n) average from the call stack. It's O(n) worst case when the pivot is always the extreme element and there's no tail-call optimization.
Bubble sort is in the table. You will not use it in production. Nobody uses it in production. It is here because interviewers ask about it and because CS professors need to explain swaps to someone.
O(n log n) Is a Proof, Not a Coincidence
Every comparison-based sort requires at least Ω(n log n) comparisons in the worst case. This is not a guideline. It is a theorem, and knowing it is what separates "I memorized the table" from "I actually understand sorting."
A comparison sort is a binary decision tree. Each internal node is one comparison. Each leaf is one possible ordering of the input. There are n! possible orderings, so the tree needs at least log₂(n!) leaves' worth of height. Stirling's approximation gets you log₂(n!) ≈ n log n.
Merge sort achieves this bound exactly, which makes it theoretically optimal among comparison sorts. See What Is a Comparison Sort? for the full decision tree proof.
The three linear-time sorts (counting, radix, bucket) sidestep the bound entirely because they never compare elements. They exploit structure in the data instead of asking "is A bigger than B?" over and over.
Stalin Sort achieves O(n) by removing any element that isn't in order. Genuinely O(n). The elements are simply gone. Not all heroes wear capes.
Which Algorithm When (This Is the Actual Interview Question)
This is the decision most interviews are testing. Not whether you can recite the table. Whether you understand why each row exists.
General purpose, in-memory data: Quicksort. It wins in practice because it sorts in-place and accesses memory sequentially during partition, giving excellent cache behavior. Use a random pivot or median-of-three to avoid the O(n²) worst case on already-sorted input.
Guaranteed O(n log n) worst case: Merge sort or heap sort. Merge sort is stable and easier to implement correctly. Heap sort uses O(1) space but has worse cache performance in practice.
Need stable sort: Merge sort. Stability matters when you sort by one key and then a second: the relative order from the first sort is preserved. Selection sort and standard quicksort are unstable.
Nearly sorted data or small arrays (n less than 64): Insertion sort. It runs in O(n) when the data is already in order, and its inner loop is tight enough to beat asymptotically faster algorithms on small inputs. This is exactly why TimSort uses insertion sort as its base case.
Sorting a linked list: Merge sort. Quicksort requires random access to find and partition around a pivot efficiently. Merge sort only needs to find the midpoint via slow-fast pointer, then merge two sorted halves.
Integer keys, small range k: Counting sort. O(n + k) time and O(k) space. If k is much larger than n, the space cost dominates and it stops being worth it.
Integer keys, fixed width: Radix sort. Process one digit position at a time using counting sort as the subroutine. d passes at O(n + k) each gives O(d(n + k)) total.
Uniformly distributed floats in [0, 1): Bucket sort. Scatter into n buckets, sort each with insertion sort, concatenate. Average O(n), degrades to O(n²) when the distribution is skewed.
O(1) auxiliary space required: Heap sort. The only O(n log n) worst-case sort with no extra allocation. Expect worse constants than quicksort on most real inputs.
Your Language Already Made a Choice
Most of the time you are not picking a sorting algorithm. Your language picked one for you, and knowing what it picked is its own interview signal.
Python: TimSort. A hybrid of merge sort and insertion sort invented by Tim Peters in 2002. It detects existing runs in the input (ascending or descending subsequences), reverses descending ones, and merges with a strategy that minimizes comparisons. Stable. Used by both list.sort() and sorted().
Java: Objects use TimSort. Primitive arrays (int[], long[]) use dual-pivot quicksort, which chooses two pivots and creates three partitions. Generally faster than single-pivot quicksort on real data.
JavaScript: TimSort in V8. The ECMAScript 2019 spec mandated that Array.prototype.sort must be stable, so all modern engines guarantee it now. Before 2019, different browsers would sort the same array differently. This was fine.
C++: std::sort uses introsort: quicksort by default, switching to heapsort if recursion depth exceeds 2 * log₂(n) to prevent O(n²) worst case, falling back to insertion sort on small subarrays. Not stable. Use std::stable_sort for stability.
Go: slices.Sort uses pdqsort (pattern-defeating quicksort), a more sophisticated introsort variant that handles common patterns like already-sorted data without degrading. Not stable. slices.SortStable uses a stable merge sort.
Rust: slice::sort is TimSort (stable). slice::sort_unstable is pdqsort, faster in practice when stability is not required.
Merge Sort: One Character Makes It Break
Split in half, recurse on each half, merge the two sorted halves. The merge step takes O(n) and happens at O(log n) levels.
Recurrence: T(n) = 2T(n/2) + O(n), which the Master Theorem resolves to O(n log n). Case 2: a = b^d, where a = 2, b = 2, d = 1.
The key invariant in the merge step: advance the pointer at the smaller current element. Use <= instead of < to preserve stability. Change it to < and equal elements from the right half will jump ahead of equal elements from the left half. Your sort still produces a sorted array. It is no longer stable. One character.
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # <= preserves stability result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result
Quicksort: Partition Does the Real Work
Choose a pivot, partition the array so everything smaller sits left and everything larger sits right, then recurse on each side. The pivot lands in its final sorted position after each partition call. That is the key insight. Everything else is bookkeeping.
See What Is a Partition in Quicksort? for the full Lomuto and Hoare variants side by side. The short version:
def quicksort(arr, low, high): if low < high: pivot_idx = partition(arr, low, high) quicksort(arr, low, pivot_idx - 1) quicksort(arr, pivot_idx + 1, high) def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1
The O(n²) worst case triggers when the pivot is always the smallest or largest element, creating partitions of size 0 and n-1 every time. Already-sorted input with a last-element pivot hits this. Random pivot selection avoids it in expectation.
When there are many duplicate values, use three-way partitioning (Dutch national flag). Standard partitioning re-examines equal elements. Three-way creates three groups (< pivot, = pivot, > pivot) and skips all equal elements in future recursions. This turns O(n²) on an all-equal array into O(n).
Heap Sort: Build-Heap Is O(n) and That Surprises Everyone
Heap sort builds a max-heap, then repeatedly extracts the max to the end of the array. The extraction loop is O(n log n). The build step looks like it should be O(n log n) too, because you call sift-down on n/2 elements and sift-down is O(log n).
Build-heap via sift-down is O(n), not O(n log n). This is one of the most common heap sort interview questions, and most candidates get it wrong.
The key is that most nodes are near the bottom. Half the nodes are leaves and do zero work. A quarter do O(1) work, an eighth do O(2) work, and so on. The sum telescopes to O(n). The O(n log n) mistake happens when you sift-up from the beginning instead. That distinction is covered at Heap Sort: Build-Heap Is O(n).
What Interviewers Are Testing (It's Not the Table)
Sorting questions almost never ask you to implement a sort from scratch. They ask you to reason about one.
- "Which sort would you use here, and why?" Tests the decision logic above.
- "What does stable mean, and when does it matter?" Tests correctness reasoning on multi-key sorting.
- "Why is quicksort usually faster than merge sort in practice?" Cache locality and no auxiliary allocation.
- "How would you sort a linked list?" Merge sort. No random access needed.
- "Can you sort this in O(n)?" Tests whether you recognize integer keys with bounded range.
- "What's the recurrence for merge sort?" T(n) = 2T(n/2) + n → O(n log n).
- "What does Python's sorted() use internally?" TimSort.
The candidates who fail sorting questions usually know the complexity table but cannot explain the why behind any row in it.
Every sorting algorithm you just studied. Every problem you will actually work on Monday.
If you want to practice walking through these trade-offs under real interview conditions, SpaceComplexity runs voice-based mock DSA interviews with rubric-based feedback on technical communication, not just whether you got the right answer.