Sorting is the algorithm an interviewer already knows the answer to, which is exactly why they ask about it: they are not testing whether you can produce a sorted list (Python's sorted() does that), they are testing whether you understand the trade-offs well enough to justify a choice. Every database index build, every "top-k" feature, every deduplication step, every ORDER BY clause bottoms out in one of these algorithms or a close cousin of one. A browser's tab-sorting-by-last-visited, a leaderboard, a merge step in a distributed log compaction job — all sorting. The reason there are seven algorithms worth knowing instead of one "best" one is that no sort wins on every axis: time, extra memory, stability, and behavior on already-mostly-sorted data all pull in different directions, and the right answer depends on which one your problem actually cares about.
def bubble_sort(a):
n = len(a)
for i in range(n):
did_swap = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
did_swap = True
if not did_swap:
breaki, the largest i + 1 values are parked at the end.range(n - 1 - i): the inner loop stops before the already-sorted suffix, so each pass is one shorter.did_swap is the early exit: a pass with no swaps means the array is sorted. That is why bubble sort is O(n) on already-sorted input.def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = keya[0..i-1] is always sorted. Each loop takes the next element, key = a[i], and inserts it into that sorted part.j walks left from the end of the sorted part.j is bigger than key, shift it one slot right to open a gap. Using > (not >=) leaves equal elements in order, which keeps the sort stable.a[j + 1] = key drops the key into the gap. On nearly-sorted input the while loop barely runs, so insertion sort is close to O(n).All three are Θ(n²) in the worst case because each does roughly n passes over roughly n elements: bubble sort does up to n-1 comparisons per pass for n-1 passes, selection sort scans the remaining unsorted slice on every pass, and insertion sort can shift an element all the way from position i back to position 0. But "same Big-O" hides real differences an interviewer wants you to name. Bubble sort does the most element writes (a swap is 3 assignments) and is the one nobody uses in production — it exists as a teaching example. Selection sort does the fewest writes of the three (exactly one swap per pass, at most n-1 swaps total), which matters when writes are expensive (e.g. flash memory), but it does not adapt to input order — it does the same number of comparisons whether the array is sorted or reversed. Insertion sort is the one that actually matters in practice: on a nearly-sorted array its inner while loop barely runs (best case Θ(n), when nothing needs to shift), it is stable, it sorts in place, and it needs no extra memory — which is why real sorting libraries switch to insertion sort for small sub-arrays (see the hybrid-sort Deep Dive below).
The precise reason each is O(n²) and not O(n): a single pass is O(n) work, and you need O(n) passes because each pass only guarantees one more element (bubble sort's largest, selection sort's minimum, insertion sort's newly-placed key) is in its final position. O(n) passes of O(n) work each is O(n) × O(n) = O(n²) — the two loops are nested, not sequential, so their costs multiply, not add.
def merge_sort(a):
if len(a) <= 1:
return a[:]
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:]); result.extend(right[j:])
return resultmid and sort each half recursively; the recursion builds the whole tree above.i and j point at the smallest not-yet-used element of each sorted half.left[i] and right[j]. Each comparison places one element, so merging n elements is O(n).<= takes from the left half on ties, so equal elements keep their order: merge sort is stable.result list is the O(n) extra memory merge sort needs.Merge sort splits the array in half recursively until each piece has one element (trivially sorted), then merges pairs of already-sorted pieces back together. The merge step is the whole trick: given two sorted lists, you can produce one sorted list by walking a pointer through each and always taking the smaller front element, which is O(a+b) — linear in the combined size, no backtracking needed. That single fact is why merge sort's total cost is Θ(n log n) in every case, not just on average: there are always exactly log₂n levels of splitting (halving n until you reach 1), and every level does a total of O(n) merge work across all its sub-merges combined, because every element gets touched exactly once per level. log₂n levels × O(n) work per level = O(n log n), with no dependence on the input's starting order — this is the guarantee quicksort cannot make.
The cost of that guarantee is memory: the merge step needs a second array to write the merged result into (you cannot merge two sorted halves back into the same array in place without overwriting elements you still need), so merge sort uses O(n) auxiliary space, on top of the O(log n) recursion-stack space every divide-and-conquer algorithm pays. That is the concrete trade merge sort makes against quicksort: predictable Θ(n log n) time, at the cost of O(n) extra memory and generally more constant-factor overhead from allocating and copying sub-arrays.
def partition(a, lo, hi):
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return ipivot = a[hi]: Lomuto partition uses the last element as the pivot.i marks where the next small element should go. Everything left of i is already known to be < pivot.j scans every other element once, so partitioning is O(n).a[j] is smaller than the pivot, swap it into slot i and grow the small region.i, between the small and large regions. That is its final position, and quicksort then recurses on [lo, i-1] and [i+1, hi].Partitioning picks a pivot, then rearranges the array so everything smaller than the pivot ends up to its left and everything bigger ends up to its right — the pivot is now in its final sorted position, with no merge step needed afterward (unlike merge sort, the recursion doesn't need to recombine anything). The partition itself is one O(n) pass with a single "boundary" index that only ever moves forward, which is why it does not need the extra array merge sort needs — it rearranges in place.
The average case is Θ(n log n) because a reasonably-chosen pivot splits the array into two roughly-equal halves, giving the same log₂n-levels-times-O(n)-work shape as merge sort. The worst case is Θ(n²) and it is not a rare edge case — it is exactly what happens with a naive "always pick the last element" pivot on an array that is already sorted (or reverse-sorted): the pivot is always the smallest or largest remaining element, so every partition splits the array into a piece of size 0 and a piece of size n-1, giving n levels of recursion instead of log₂n, each doing O(n) work — that's the O(n²) you can see directly in the comparison counts above (28 vs 14 comparisons for the same array size, just reordered). Real implementations defend against this with randomized pivot selection, "median of three" (compare first/middle/last and pick the median), or by switching to insertion sort on small partitions — but if you naively pivot on a fixed position, a sorted or adversarially-constructed input is a genuine O(n²) trap, not a theoretical curiosity.
Heap sort's full mechanics (the array-as-tree index math, heapify-up, heapify-down, and why building a heap from scratch is O(n) rather than O(n log n)) belong on the heaps page — see the Heaps Deep Dive for the worked walkthrough. The short version for this page: build a max-heap out of the whole array in O(n), then repeatedly swap the root (the current maximum) with the last unsorted element and shrink the heap by one, restoring the heap property with an O(log n) "sift down" each time. That is n removals at O(log n) each, giving Θ(n log n) in every case — like merge sort it has no bad input, unlike merge sort it needs no extra array (the heap lives in the same array being sorted), which is its real selling point: guaranteed n log n time and O(1) extra space. The trade is that it is not stable (swapping across the array can reorder equal elements) and it has worse cache behavior than quicksort, because heap operations jump around the array by index math (parent/child) rather than scanning it sequentially, so in practice it tends to lose a well-tuned quicksort on random data despite matching its average-case complexity.
def counting_sort(a):
lo, hi = min(a), max(a)
counts = [0] * (hi - lo + 1)
for x in a:
counts[x - lo] += 1
out = []
for i, c in enumerate(counts):
out.extend([i + lo] * c)
return outcounts gets one slot per possible value: k = hi − lo + 1 slots.counts[x - lo] += 1 tallies each value. Subtracting lo lets the range start anywhere, not just at 0.c times. Index order is value order, so the output is sorted.Counting sort never compares two elements to each other — that is the whole point. It counts how many times each value occurs (a single O(n) pass builds the counts array, indexed by value), then reads the counts back out in value order to produce the sorted output (a second O(k) pass, where k is the range of possible values). Total cost is O(n+k): one pass over the input, one pass over the value range. This is why it can beat Θ(n log n) — the n log n lower bound only applies to comparison-based sorts (it comes from the fact that a comparison sort is really navigating a decision tree with n! leaves, one per possible ordering, and you need log₂(n!) ≈ n log n comparisons to distinguish between them). Counting sort sidesteps that whole argument by never asking "is a < b" — it asks "what is a", which is a stronger requirement, and that is exactly the thing it trades away: it only works on data with a small, known, ideally-integer range. Sort a million 32-bit floating point salaries and k is unusably huge; sort a million exam scores from 0-100 and k=101 makes counting sort dramatically faster than any comparison sort, genuinely O(n) for fixed k.
def radix_sort(a):
exp = 1
while max(a) // exp > 0:
buckets = [[] for _ in range(10)]
for x in a:
buckets[(x // exp) % 10].append(x)
a = [x for bucket in buckets for x in bucket]
exp *= 10
return aexp selects the digit: 1 for ones, 10 for tens, 100 for hundreds.(x // exp) % 10 pulls out the current digit, and the number goes into that digit's bucket (0–9).Radix sort also avoids comparisons, but instead of counting whole values it counts sort by one digit at a time, starting from the least significant digit, using counting sort as the subroutine for each digit pass (that's why each pass is stable — it has to be, or the previous passes' work gets scrubbed out). After sorting by the 1s digit, numbers that share a 1s digit are grouped but not yet correctly ordered relative to their other digits; the crucial insight is that sorting by the next digit up, as a stable sort, preserves the relative order established by the previous, less-significant digit — so by the time you've processed the most significant digit, the whole array is correctly ordered. With d digits and a base-10 counting sort per digit (k=10 buckets, O(n+k) per pass), the total cost is O(d·(n+k)) = O(d·n) for fixed base. This beats n log n whenever d is small relative to log n — sorting 8-digit account numbers is O(8n), much better than O(n log n) once n is large — but if d grows with the data (e.g. sorting arbitrary-precision numbers or long strings), the advantage erodes, since d itself starts to dominate.
A sort is stable if it preserves the original relative order of elements that compare equal. This matters the instant you sort by more than one key: sort a list of people by first name, then stably sort the result by last name, and everyone with the same last name is still in first-name order inside their group — you effectively get a multi-key sort "by last name, then by first name" for free, without writing a compound comparator. Run the same two steps with an unstable sort and the first-name ordering inside each last-name group is undefined — it might happen to survive by accident on a given implementation, or it might not, and you cannot rely on it. This is not a theoretical concern: spreadsheet "sort by column A, then column B" UIs, multi-level ORDER BY fallbacks, and re-sorting a already-sorted UI list by a new column all depend on stability to behave the way users expect. Merge sort and insertion sort are naturally stable (the merge step and the shift both prefer "keep earlier elements first" when values tie); a naive selection sort and the in-place partitioning step of quicksort are not, because they swap elements across the array rather than shifting them, and a swap can leapfrog an equal element out of its original position.
All seven algorithms, run on the same random array, plus a worst-case demonstration for quicksort and a stability demonstration.
import random
def bubble_sort(a):
a = a[:]
n = len(a)
swaps = 0
for i in range(n):
did_swap = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swaps += 1
did_swap = True
if not did_swap:
break
return a, swaps
def selection_sort(a):
a = a[:]
n = len(a)
writes = 0
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
a[i], a[min_idx] = a[min_idx], a[i]
writes += 1
return a, writes
def insertion_sort(a):
a = a[:]
shifts = 0
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
shifts += 1
a[j + 1] = key
return a, shifts
def merge_sort(a):
if len(a) <= 1:
return a[:]
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:]); result.extend(right[j:])
return result
def quicksort(a):
a = a[:]
comparisons = [0]
def helper(lo, hi):
if lo >= hi:
return
pivot = a[hi]
i = lo
for j in range(lo, hi):
comparisons[0] += 1
if a[j] < pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
helper(lo, i - 1)
helper(i + 1, hi)
helper(0, len(a) - 1)
return a, comparisons[0]
def counting_sort(a):
if not a:
return []
lo, hi = min(a), max(a)
counts = [0] * (hi - lo + 1)
for x in a:
counts[x - lo] += 1
out = []
for i, c in enumerate(counts):
out.extend([i + lo] * c)
return out
def radix_sort(a):
if not a:
return []
a = a[:]
max_val = max(a)
exp = 1
while max_val // exp > 0:
buckets = [[] for _ in range(10)]
for x in a:
buckets[(x // exp) % 10].append(x)
a = [x for bucket in buckets for x in bucket]
exp *= 10
return a
random.seed(42)
arr = [random.randint(1, 50) for _ in range(8)]
print("input array :", arr)
print("bubble sort ->", bubble_sort(arr))
print("selection sort->", selection_sort(arr))
print("insertion sort->", insertion_sort(arr))
print("merge sort ->", merge_sort(arr))
print("quicksort ->", quicksort(arr))
print("counting sort ->", counting_sort(arr))
print("radix sort ->", radix_sort(arr))
people = [("Doe", "Zack"), ("Smith", "Amy"), ("Doe", "Amy"), ("Lee", "Amy")]
by_first = sorted(people, key=lambda p: p[1])
print("sorted by first name :", by_first)
print("then stable by last :", sorted(by_first, key=lambda p: p[0]))
sorted_input = list(range(8))
_, sorted_comparisons = quicksort(sorted_input)
random_input = [random.randint(1, 100) for _ in range(8)]
_, random_comparisons = quicksort(random_input)
print("quicksort comparisons on SORTED input:", sorted_comparisons, "for n =", len(sorted_input))
print("quicksort comparisons on RANDOM input:", random_comparisons, "for n =", len(random_input))
# Output:
# input array : [41, 8, 2, 48, 18, 16, 15, 9]
# bubble sort -> ([2, 8, 9, 15, 16, 18, 41, 48], 17)
# selection sort-> ([2, 8, 9, 15, 16, 18, 41, 48], 5)
# insertion sort-> ([2, 8, 9, 15, 16, 18, 41, 48], 17)
# merge sort -> [2, 8, 9, 15, 16, 18, 41, 48]
# quicksort -> ([2, 8, 9, 15, 16, 18, 41, 48], 15)
# counting sort -> [2, 8, 9, 15, 16, 18, 41, 48]
# radix sort -> [2, 8, 9, 15, 16, 18, 41, 48]
# sorted by first name : [('Smith', 'Amy'), ('Doe', 'Amy'), ('Lee', 'Amy'), ('Doe', 'Zack')]
# then stable by last : [('Doe', 'Amy'), ('Doe', 'Zack'), ('Lee', 'Amy'), ('Smith', 'Amy')]
# quicksort comparisons on SORTED input: 28 for n = 8
# quicksort comparisons on RANDOM input: 14 for n = 8a = a[:], working on a copy so the same random input can be fed to all of them.bubble_sort, selection_sort and insertion_sort also return a counter (swaps, writes, shifts). Selection sort does only 5 writes against 17 for the others: it makes at most n−1 swaps, useful when writes are expensive.merge_sort and quicksort are the code from the diagrams. quicksort counts comparisons so you can compare sorted and random input.counting_sort and radix_sort never compare two elements with each other.people lines show stability: Python's sorted is stable, so sorting by last name keeps the first-name order among the Does.Selection sort's 5 writes versus bubble and insertion sort's 17 shifts on the same array is the concrete version of "selection sort minimizes writes" from the Deep Dive above — and the 28-vs-14 comparison counts for quicksort on sorted versus random input of the same size is the concrete version of "naive-pivot quicksort degrades on sorted input."
Q: Why is comparison-based sorting's best possible worst-case Θ(n log n)?
A: A comparison sort can be modeled as a binary decision tree where each internal node is one comparison and each leaf is one of the n! possible orderings of the input. To distinguish between n! outcomes with yes/no comparisons you need a tree of depth at least log₂(n!), and by Stirling's approximation log₂(n!) is Θ(n log n). So no algorithm that only learns information via pairwise comparisons can beat that bound in the worst case — merge sort and heap sort actually achieve it.
Q: Why does quicksort have a bad worst case despite being fast on average — what causes it?
A: Quicksort's cost depends entirely on how balanced each partition is. With a good pivot each partition splits the array roughly in half, giving log₂n levels of recursion. With a naive fixed-position pivot (e.g. always the last element) on an already-sorted or reverse-sorted array, the pivot is always the extreme value, so every partition produces one empty side and one side of size n-1 — that's n levels instead of log₂n, each doing O(n) partition work, giving Θ(n²).
Q: What's the actual difference between merge sort and quick sort's space usage?
A: Merge sort needs O(n) auxiliary space because its merge step combines two sorted sub-arrays into a new array (you cannot merge two sorted halves back into the same buffer in place without clobbering unread elements). Quicksort partitions in place, using only the O(log n) space of its recursion stack in the average balanced case — though a badly unbalanced quicksort can use O(n) stack depth in the worst case too.
Q: What does "stable sort" mean, and give a real example of when it matters?
A: A stable sort preserves the original relative order of elements whose sort key compares equal. Example: sort a spreadsheet of orders by customer name, then stably sort the result by order date — orders from the same date stay grouped in customer-name order, effectively giving you "sort by date, then by name" without writing a two-key comparator. An unstable sort would scramble that secondary order.
Q: Why can counting sort beat the n log n lower bound — what's it trading away?
A: The n log n bound only applies to algorithms that sort purely by comparing pairs of elements. Counting sort never compares two elements — it counts occurrences of each value and reads them back out in order, costing O(n+k) for k possible values. What it trades away is generality: it needs the key space to be small and (practically) integer-valued, so it cannot sort arbitrary comparable objects the way merge sort or quicksort can.
Q: When would you choose insertion sort over quicksort despite it being O(n²)?
A: On small arrays (roughly under 10-50 elements depending on constants) or nearly-sorted data, where insertion sort's low overhead and Θ(n) best case beat quicksort's recursion and partitioning overhead. This is not a hypothetical — real hybrid sorts explicitly switch to insertion sort once a sub-array shrinks below a threshold, because at that size the asymptotic advantage of n log n doesn't outweigh the constant-factor cost of recursive partitioning.
Q: What's a hybrid sort and why do real languages use one (e.g. Timsort)?
A: A hybrid sort combines multiple strategies to exploit each one's strengths: Python and Java's Timsort finds existing sorted "runs" in the input (real-world data is often partially sorted already), merges those runs efficiently, and uses insertion sort for small runs. No single algorithm dominates on every input shape, so production sorts detect structure (already-sorted runs, small sizes) and adapt instead of committing to one fixed strategy.
Follow-up: If quicksort's worst case is Θ(n²), why is it still the default general-purpose sort in many standard libraries (e.g. C's qsort, or was, for years)?
A: Because average-case performance and constant factors dominate real-world usage far more often than the worst case does, and the worst case is defensible against: randomized pivot selection (or median-of-three) makes the Θ(n²) input-dependent trap effectively impossible for an adversary or ordinary data to trigger reliably, turning it into an expected-case guarantee rather than an input-order-dependent one. In practice quicksort also sorts in place with excellent cache locality, which real hardware rewards heavily.
Follow-up: You need to sort 10 million fixed-length 16-character strings as fast as possible. Would you reach for radix sort?
A: Possibly — radix sort works on strings too, treating each character position as a "digit" with a base-256 (or smaller) alphabet, sorted from least significant (rightmost) character to most, same as with numbers. With d=16 fixed-length characters, that's O(16 × (n + 256)) = O(16n), which can beat O(n log n) ≈ O(23n) for n=10 million. The catch is the constant factor and memory churn of 16 counting-sort passes with 256-bucket arrays each; in practice you'd benchmark against a well-tuned comparison sort (like Timsort, which handles variable structure gracefully) before committing, since radix sort's theoretical win doesn't always survive real cache and allocation overhead.
Follow-up: What if you need a sort that's both O(n log n) worst-case AND stable AND O(1) extra space — can you have all three?
A: Not with any of the seven algorithms here — this is a genuine open trade-off, not an oversight. Merge sort gives worst-case n log n and stability but needs O(n) space (in-place merge variants exist but are far slower in practice, effectively O(n log²n)). Heap sort gives worst-case n log n and O(1) space but is unstable. Quicksort can be made to use O(log n) space but isn't stable and isn't worst-case n log n without extra machinery (like introsort's fallback to heap sort). You generally pick two of the three and design around the third.
The wrong choice usually comes from optimizing for the wrong axis. Reach for merge sort when you need a hard n log n guarantee and can afford O(n) extra memory — external sorting (data too big for RAM) and linked-list sorting (where merge sort's sequential access pattern needs no random indexing) are its natural homes. Reach for a well-tuned (randomized-pivot) quicksort as the default general-purpose in-memory sort when average speed and low memory matter more than a worst-case guarantee — which is most of the time, which is why it (or a hybrid built on it) is a common library default. Reach for heap sort specifically when you need the O(1)-space guarantee that quicksort can't promise and merge sort can't either, and you can tolerate losing stability and some real-world speed. Reach for counting or radix sort only when the data has exploitable structure — small integer ranges or fixed-width keys — because outside that structure they are either wrong (unbounded/non-integer keys) or no better than a comparison sort once k or d grows large. And reach for plain insertion sort, not a "serious" algorithm, whenever the array is small or already nearly sorted, since that's the one case where an O(n²) algorithm is the objectively fast choice. When in doubt and the language gives you a built-in sort, use it — Timsort and its relatives already encode most of this decision tree.