The five algorithms worth knowing cold
Bubble sort and insertion sort are the two simple quadratic methods. Bubble sort repeatedly walks the list swapping adjacent out-of-order pairs, letting the largest value bubble to the end on each pass. Insertion sort builds the sorted result one element at a time, sliding each new value back into its correct spot like ordering a hand of cards. Both are O(n squared) and rarely used on large data, but insertion sort is genuinely fast on small or nearly-sorted inputs, which is why real libraries switch to it for tiny subarrays.
Merge sort and quicksort are the two classic divide-and-conquer sorts. Merge sort splits the array in half, sorts each half recursively, then merges the two sorted halves; it is stable and runs in O(n log n) every time, but needs O(n) extra space. Quicksort picks a pivot, partitions elements into those below and above it, then recurses on each side; it sorts in place and is usually the fastest in practice, but a poor pivot can degrade it to O(n squared).
Heap sort builds a binary heap from the array, then repeatedly extracts the maximum to fill the end of the array. It guarantees O(n log n) time with O(1) extra space, but it is not stable and tends to run slower than quicksort in practice because it jumps around memory instead of scanning it linearly.
Stability: when equal elements must keep their order
A sort is stable if elements that compare equal keep their original relative order. Suppose you sort a list of users by name, then by age — a stable sort preserves the name ordering within each age group, so the final result is sorted by age and then by name for free. Merge sort, insertion sort, and bubble sort are stable; standard quicksort and heap sort are not.
This is why Python's sorted() and list.sort() use Timsort, a stable hybrid of merge and insertion sort. When an interviewer asks you to sort by multiple keys or to preserve input order among ties, reach for a stable algorithm — or sort by a tuple of keys so stability never becomes a problem.
Why O(n log n) is the wall for comparison sorts
No comparison-based sort can beat O(n log n) in the worst case, and this is a proven lower bound rather than just an observation. The argument: a sort that only compares pairs of elements is a decision tree, and to distinguish all n! possible orderings the tree needs at least n! leaves. A binary tree with n! leaves has height at least log2(n!), which works out to Theta(n log n). So merge and heap sort are asymptotically optimal for comparison sorting.
You can go faster only by not comparing elements directly. Counting sort, radix sort, and bucket sort reach linear time by exploiting structure — small integer ranges or fixed-width keys — instead of pairwise comparisons. They are the standard answer when an interviewer asks how you could sort faster than O(n log n).
def merge_sort(nums):
if len(nums) <= 1:
return nums # 0 or 1 element is already sorted
mid = len(nums) // 2
left = merge_sort(nums[:mid]) # sort each half recursively
right = merge_sort(nums[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves order of equals (stable)
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
merged.extend(left[i:]) # append whatever remains
merged.extend(right[j:])
return mergedBest/worst/average differ: insertion sort reaches O(n) on nearly-sorted data, quicksort averages O(n log n) but degrades to O(n^2) with poor pivots, while merge and heap sort stay O(n log n) in every case.
When to use it
- You need a guaranteed O(n log n) worst case and stable output — use merge sort or a library Timsort.
- The input is small (a few dozen elements) or nearly sorted — insertion sort is simple and genuinely fast here.
- You must sort in place with O(1) extra memory and a firm worst-case bound — heap sort fits.
- You want the fastest average-case in-memory sort and can guard against bad pivots — quicksort, as most standard libraries use it.
Watch out for
- Assuming quicksort is always O(n log n). With a naive pivot, already-sorted or reverse-sorted input drops it to O(n^2); real implementations randomize the pivot or fall back to heap sort to avoid this.
- Forgetting that standard quicksort and heap sort are not stable, so sorting by a secondary key can silently reorder ties — use a stable sort or sort by a key tuple instead.
- Reimplementing a sort by hand when the language's built-in is correct, faster, and what the interviewer expects — only hand-roll one when explicitly asked to.
Sorting shows up in interviews in three ways. First, as a warm-up implementation question — "code merge sort" or "implement quicksort" — where the interviewer watches for a correct partition or merge step, clean recursion, and correct base cases. Second, as a knowledge check: they will ask which algorithms are stable, what quicksort's worst case is and why, or to sketch the O(n log n) lower bound. Third, and most often, sorting is a preprocessing step inside a larger problem — sort the intervals, then sweep; sort the array, then use two pointers — and the real signal is whether you recognize that sorting unlocks a simpler solution. Knowing the complexities, stability, and trade-offs cold matters far more than memorizing every implementation line by line.