Sorting Algorithms: Time Complexity Cheat Sheet for Interviews
Sorting is one of the most frequently tested topics in coding interviews. You rarely need to implement a full sort from scratch, but you must know the time and space trade-offs cold, and explain why your chosen approach fits the problem constraints.
Why Do Interviewers Ask About Sorting?
Many problems reduce to "find the k-th element" or "group similar items," and sorting is often the brute-force baseline an interviewer expects you to name before you optimize past it. Follow-ups probe whether you know faster alternatives, like heaps, counting sort, or bucket sort, once the brute force is on the table. System design loops sometimes ask how databases or distributed systems sort datasets too large to fit in memory, which is a different question again from sorting an array in place.
What Do Stable and In-Place Actually Mean?
These two words show up in almost every answer below, so define them once instead of guessing from context. A sort is stable when two elements with equal keys keep their original relative order after sorting, which matters the moment you sort by one field and need a second field's order preserved (sort a list of orders by status, and same-status orders should stay in their original date order). A sort is in-place when it uses O(1) or O(log n) extra memory beyond the input itself, rather than allocating a second array the size of the input. Neither property affects the final sorted values, but both affect whether a sort is the right tool for a specific interview constraint.
How Do the Comparison-Based Sorts Compare?
Bubble Sort
O(n²) time and O(1) space, comparing adjacent pairs and swapping them into order. Simple but almost never the right answer in interviews, so mention it only to contrast with better options.
Selection Sort
O(n²) time and O(1) space, repeatedly picking the minimum from the unsorted portion. Still O(n²), but it performs fewer swaps than bubble sort, and it is rarely used in practice.
Insertion Sort
O(n) best, O(n²) average and worst, O(1) space. Builds a sorted prefix one element at a time and does well on nearly sorted data or small n, often under 50 elements. Python's Timsort uses insertion sort for small runs for exactly this reason.
Shell Sort
O(n log n) to O(n²) depending on the gap sequence, O(1) space. A generalization of insertion sort: compare and swap elements far apart first, using a shrinking gap sequence, then narrow the gap down to 1. It moves out-of-place elements into position faster than plain insertion sort, and while you are rarely asked to implement it, it is a good answer when asked how you would speed up insertion sort without extra memory.
Merge Sort
O(n log n) time in all cases, O(n) space. Divide the array in half, sort each half, merge the results. Stable and predictable, and the right call when you need a guaranteed O(n log n) regardless of input order, though the extra memory for the merge step is the trade-off you are accepting.
Quick Sort
O(n log n) average, O(n²) worst, O(log n) space for the recursion stack. Pick a pivot, partition around it, recurse on both sides. In-place and cache-friendly, which is why it is the default in most standard libraries when paired with a randomized pivot or introsort to avoid the worst case, though it is unstable unless implemented with extra care.
Heap Sort
O(n log n) time in all cases, O(1) space. Build a max-heap, then repeatedly extract the maximum. It guarantees O(n log n) with no extra array, but its constants run slower than quicksort's in practice, so reach for it when memory is tight and you need a worst-case guarantee, not as a default.
Timsort
O(n log n) worst case, O(n) best case for already-sorted runs, O(n) space. A hybrid of merge sort and insertion sort: it splits the input into small runs, sorts each run with insertion sort, then merges runs with merge sort's merge step. It is stable and adapts well to partially sorted real-world data, and it is what Python's sorted() and list.sort(), and Java's Arrays.sort() for objects, actually use in production, which is worth naming if you are asked what a language's built-in sort really does under the hood.
How Do the Non-Comparison Sorts Compare?
Counting Sort
O(n + k) time, O(k) space, where k is the range of input values. Works when values are small integers in a known range, and it is stable when implemented with prefix sums.
Radix Sort
O(d(n + k)) time, where d is the number of digits per pass. Sorts digit by digit using a stable sub-sort, usually counting sort, and it suits fixed-width integers or strings of bounded length.
Bucket Sort
O(n) average when inputs are spread evenly across buckets, O(n²) worst if every element lands in one bucket. Good for floating-point values in the range [0, 1).
What Is the Quick Reference for Every Sort's Complexity?
Bubble Sort: O(n²), O(1) space, stable. Selection Sort: O(n²), O(1) space, unstable. Insertion Sort: O(n²) average, O(n) best, O(1) space, stable. Shell Sort: O(n log n) to O(n²), O(1) space, unstable.
Merge Sort: O(n log n), O(n) space, stable. Quick Sort: O(n log n) average, O(n²) worst, O(log n) stack, unstable. Heap Sort: O(n log n), O(1) space, unstable.
Timsort: O(n log n) worst, O(n) best, O(n) space, stable. Counting Sort: O(n + k), O(k) space, stable. Radix Sort: O(n · d), O(n + k) space, stable. Bucket Sort: O(n) average, O(n) space, stable.
Why Is There an n log n Lower Bound on Comparison Sorts?
Any comparison-based sort must make at least Omega(n log n) comparisons in the worst case, because a comparison sort's decision tree needs enough leaves to represent every possible ordering of n items, and that forces at least log2(n!) comparisons, which is Omega(n log n). That is why merge sort, heap sort, and quicksort on average are considered optimal for general comparison sorting: you cannot do meaningfully better without exploiting some structure already present in the input, like a bounded value range or partial ordering.
What Sort Does Each Language Actually Use by Default?
Interviewers sometimes ask this directly, and the honest answer is more nuanced than "quicksort" for every language.
JavaScript (V8) and Python both use Timsort, the hybrid described above: small runs get insertion sort, larger runs get merged with merge sort's merge step. Both are stable and O(n log n) worst case.
Java splits by type: Arrays.sort on primitive arrays (int[], double[]) uses a dual-pivot quicksort, which is unstable but avoids the O(n) allocation a stable sort would need. Arrays.sort and Collections.sort on object arrays and Lists use Timsort instead, since object comparisons already pay for indirection and stability matters more when you are sorting records, not raw numbers.
C++'s std::sort is typically introsort: it starts as quicksort for speed, switches to heapsort if the recursion depth gets too deep (guarding against quicksort's O(n²) worst case), and drops to insertion sort for small partitions. It is unstable by design; reach for std::stable_sort, which is a merge sort under the hood, when order among equal keys matters.
Go's sort.Slice uses pattern-defeating quicksort (pdqsort), a modern introsort variant tuned to run closer to linear time on already-sorted or low-cardinality input. Naming the specific algorithm behind a language's default, not just "it's quicksort," is a small detail that signals you have actually read past the API docs.
Which Sort Should You Name First in an Interview?
- Default answer for general arrays: quicksort or mergesort, quicksort when in-place matters, mergesort when stability matters or worst-case O(n log n) is required
- Small or nearly sorted input: insertion sort, since its best case beats every n log n sort on data that is already close to ordered
- Need the top-k elements without a full sort: a min-heap of size k, which gets you O(n log k) instead of paying for O(n log n) on the whole array
- Integers in a small, known range: counting sort or bucket sort, trading the comparison lower bound for a linear pass
- Linked lists: mergesort, because its merge step needs only O(1) extra space per node and no random access, unlike quicksort's partitioning
Frequently Asked Questions
Why is quicksort O(n²) in the worst case?
Adversarial or already-sorted input paired with a bad pivot choice, like always picking the first or last element, causes unbalanced partitions where one side gets almost everything. Fix it with a randomized pivot, or introsort, which switches to heapsort once recursion depth exceeds a threshold.
Is mergesort or quicksort the better default?
Quicksort wins on average for in-place array sorting because of cache locality: its memory accesses stay close together, which real hardware rewards. Mergesort wins when stability is required, the data lives in a linked list, or you need predictable worst-case performance regardless of input.
Can you sort in O(n) time?
Only with non-comparison sorts, and only when the input has exploitable structure, like a bounded integer range or a fixed digit count. Otherwise no, and citing the comparison lower bound is the correct answer when an interviewer pushes for faster.
What sorting algorithm does JavaScript's Array.sort use?
V8 uses Timsort, the same hybrid of mergesort and insertion sort that Python uses, which is why both languages handle partially ordered real-world data well without any tuning from you.
What is the fastest sort for data that is already almost sorted?
Insertion sort, somewhat counterintuitively, because its best case is O(n) when the input needs only a handful of swaps to become fully sorted, which beats every O(n log n) sort's guaranteed overhead on data that barely needs touching.
Practice Tip
Before your next mock interview, pick three problems from our coding question bank and state out loud which sort, if any, you would use and why. Interviewers care less about memorizing every constant factor and more about matching the algorithm to the actual constraints: stability, memory, input distribution, and whether you need the full sorted order or just the k-th element. Time complexity fundamentals covers the Big O reasoning this cheat sheet assumes you already have, and LeetCode patterns worth recognizing on sight covers when a top-k or interval problem is really a sorting problem in disguise.