Sorting Algorithms Compared (Big O Cheat Sheet)
Bubble, insertion, merge, quick and heap sort compared by time, space, and stability. Here's which sorting algorithm to know for interviews, how the fast ones work, and why sorting first unlocks other solutions.
For coding interviews you rarely write a sorting algorithm from scratch, but you must know their Big O, how the fast ones work, and when sorting first makes a hard problem easy. The headline: general comparison sorting tops out at O(n log n) (merge, quick, heap), the naive sorts are O(n²), and you should reach for your language’s built-in sort in real answers.
Sorting matters in interviews less as a thing to implement and more as a tool: sorting the input first is the setup move for two-pointer solutions, deduplication, and many greedy algorithms.
The cheat sheet
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | no |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | no |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | no |
| Counting/radix | O(n) | O(n) | O(n) | O(n+k) | yes |
The three bold rows are the ones interviews care about. The O(n²) sorts are worth understanding conceptually, but you’d never choose them for large input. See Big O notation for what these growth rates mean in practice.
Merge sort — divide and conquer
Split the array in half, sort each half (recursively), then merge the two sorted halves:
function mergeSort(arr) {
if (arr.length <= 1) return arr; // base case
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // sort halves
const right = mergeSort(arr.slice(mid));
return merge(left, right); // combine sorted halves
}It’s a textbook example of recursion and divide-and-conquer: guaranteed O(n log n), and stable. The cost is O(n) extra space for the merge.
Quicksort — partition in place
Pick a pivot, move smaller elements left and larger ones right (partition), then recurse on each side:
- Average: O(n log n), in place with O(log n) stack space — usually the fastest in practice thanks to cache locality.
- Worst: O(n²) if pivots are consistently bad (e.g. already-sorted input with a naive pivot). Randomised or median-of-three pivots avoid this.
Most language built-ins (Arrays.sort for primitives in Java, V8’s sort, Python’s Timsort) are tuned hybrids — Timsort blends merge and insertion sort and is stable.
The real interview lesson: sort first
The highest-value reason to understand sorting is that sorting the input unlocks other techniques:
- A sorted array enables the opposite-ends two-pointer trick for pair sums.
- Sorting groups duplicates together, making dedup trivial.
- Many greedy algorithms (interval scheduling, “merge intervals”) require sorting first.
Spending O(n log n) to sort, then O(n) for the main pass, is a common and accepted O(n log n) total — and often the intended solution.
Stability — why it matters
A stable sort keeps equal elements in their original order. This is essential when sorting by multiple keys: sort by secondary key, then stably by primary key, and the secondary order is preserved within ties. Merge sort and Timsort are stable; heapsort and typical quicksort are not.
Common mistakes
- Quoting quicksort as always O(n log n) — its worst case is O(n²). Mention the pivot caveat.
- Forgetting merge sort’s O(n) space when asked about memory.
- Re-implementing sort when the built-in is expected — it wastes time and risks bugs.
- Assuming the language sort is stable — most are, but confirm for the language you’re using.
array.sort() sorts lexicographically by default — [10, 2, 1].sort() gives [1, 10, 2]. Always pass a comparator for numbers: arr.sort((a, b) => a - b).
Where this fits
Sorting sits in Phase 3 of the coding interview roadmap, built on recursion (merge/quicksort) and measured by Big O, and it’s the setup for the two-pointer pattern.
The algorithms, their trade-offs, and “sort-first” problem setups are drawn out in our job-ready tier — JavaScript in Three Months, Python in Three Months, and Java in Three Months. For non-comparison sorts (counting, radix, bucket) and external/parallel sorting at scale, the for Staff Engineers tier goes deeper: JavaScript, Python, Java.
Know the trade-offs, call the built-in, and use sorting as the setup move it usually is.
Frequently asked questions
Which sorting algorithm is fastest?
For general-purpose comparison sorting, the fastest you can do is O(n log n), achieved by merge sort, quicksort, and heapsort. Quicksort is usually fastest in practice due to good cache behaviour, though its worst case is O(n²); merge sort guarantees O(n log n) and is stable. For special cases, counting and radix sort can reach O(n).
What is the difference between merge sort and quicksort?
Merge sort divides the array, sorts each half, and merges them; it is stable and always O(n log n) but needs O(n) extra space. Quicksort partitions around a pivot and sorts in place with O(log n) space; it averages O(n log n) but degrades to O(n²) on bad pivots. Most language built-ins use a hybrid of these.
Do I need to implement sorting algorithms in interviews?
Rarely from scratch — you usually call the built-in sort. But you must know their Big O, the merge-sort and quicksort ideas, stability, and when sorting first makes a problem easier. Interviewers test understanding and trade-offs more than memorised implementations.
What is a stable sort?
A stable sort preserves the relative order of elements that compare equal. If two records have the same key, a stable sort keeps them in their original order. This matters when sorting by multiple keys in sequence — for example, sort by name, then stably by age.