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 interviewers ask about sorting

Many problems reduce to "find the k-th element" or "group similar items" — sorting is often the brute-force baseline.
Follow-ups probe whether you know faster alternatives (heaps, counting sort, bucket sort).
System design loops sometimes ask how databases or distributed systems sort large datasets.

Comparison-based sorts

Bubble Sort

O(n²) time, O(1) space. Compare adjacent pairs and swap. Simple but almost never the right answer in interviews. Mention it only to contrast with better options.

Selection Sort

O(n²) time, O(1) space. Repeatedly pick the minimum from the unsorted portion. Still O(n²) but performs fewer swaps than bubble sort. Rarely used in practice.

Insertion Sort

O(n) best, O(n²) average/worst, O(1) space. Builds a sorted prefix one element at a time. Excellent for nearly sorted data or small n (often n < 50). Python's Timsort uses insertion sort for small runs.

Merge Sort

O(n log n) time in all cases, O(n) space. Divide the array in half, sort each half, merge. Stable, predictable, and great when you need guaranteed O(n log n). Downside: extra memory for the merge step.

Quick Sort

O(n log n) average, O(n²) worst, O(log n) space for recursion stack. Pick a pivot, partition, recurse. In-place and cache-friendly — the default in most standard libraries (with randomized pivot or introsort to avoid worst case). Unstable unless implemented carefully.

Heap Sort

O(n log n) time in all cases, O(1) space. Build a max-heap, repeatedly extract the maximum. Guaranteed O(n log n) with no extra array, but slower constants than quicksort in practice. Useful when memory is tight and you need worst-case guarantees.

Non-comparison sorts

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. Stable when implemented with prefix sums.

Radix Sort

O(d · (n + k)) time where d is the number of digits/pass. Sorts digit-by-digit using a stable sub-sort (usually counting sort). Used for fixed-width integers or strings of bounded length.

Bucket Sort

O(n) average when inputs are uniformly distributed across buckets, O(n²) worst if all elements land in one bucket. Good for floating-point values in [0, 1).

Quick reference

Bubble Sort — O(n²) / O(1) / stable. Selection Sort — O(n²) / O(1) / unstable. Insertion Sort — O(n²) avg, O(n) best / O(1) / stable.

Merge Sort — O(n log n) / O(n) / stable. Quick Sort — O(n log n) avg, O(n²) worst / O(log n) stack / unstable. Heap Sort — O(n log n) / O(1) / unstable.

Counting Sort — O(n + k) / O(k) / stable. Radix Sort — O(n · d) / O(n + k) / stable. Bucket Sort — O(n) avg / O(n) / stable.

The Ω(n log n) lower bound

Any comparison-based sort must make at least Ω(n log n) comparisons in the worst case. That is why merge sort, heap sort, and quicksort (average) are optimal for general comparison sorting — you cannot do better without exploiting structure in the input.

When to say which in an interview

Default answer for general arrays: quicksort or mergesort. Quicksort for in-place; mergesort when stability matters or worst-case O(n log n) is required.
Small or nearly sorted input: insertion sort.
Need top-k elements without full sort: use a min-heap of size k — O(n log k) instead of O(n log n).
Integers in a small range: counting sort or bucket sort.
Linked lists: mergesort is natural because merge is O(1) extra space per node (no random access needed).

Common follow-up questions

Why is quicksort O(n²) worst case?

Adversarial or sorted input with a bad pivot (first/last element) causes unbalanced partitions. Fix with random pivot or introsort (switch to heapsort when recursion depth exceeds a threshold).

Is mergesort or quicksort better?

Quicksort wins on average for in-place array sorting due to cache locality. Mergesort wins when stability is required, data is linked, or you need predictable performance.

Can you sort in O(n) time?

Only with non-comparison sorts when input has structure (bounded integer range, fixed digit count). Otherwise no — cite the comparison lower bound.

What does JavaScript's Array.sort use?

V8 uses Timsort (a hybrid of mergesort and insertion sort), which adapts to partially ordered data.

Practice tip

Before your next loop, pick three problems from our coding question bank and state aloud which sort (if any) you would use and why. Interviewers care less about memorizing every constant factor and more about matching the algorithm to constraints: stability, memory, input distribution, and whether you need the full sorted order or just the k-th element.