Sorting Intuition
Quick reference
| Merge Sort | O(n log n) |
| Quick Sort | O(n log n) average, O(n²) worst case |
| Heap Sort (preview — built in Phase 5) | O(n log n) |
Sorting is a one-time investment: pay a cost once to put the data in order, and a lot of questions that would otherwise be expensive (find the median, check for duplicates, merge two lists) get cheap afterward. There are several strategies for doing the sorting itself, and they make different trade-offs.
Merge Sort splits the array in half, recursively sorts each half, then merges the two sorted halves back together — the exact divide-and-conquer shape from Recursion Basics's pow(x, n), just applied to sorting instead of exponentiation. Quick Sort instead picks a pivot value, partitions the array into "less than the pivot" and "greater than the pivot" in place, and recurses into each side. A third strategy, Heap Sort, always pulls out the current smallest (or largest) remaining element one at a time via a heap — but a heap is a structure this curriculum hasn't built yet (it's Phase 5's whole subject), so Heap Sort is previewed here by name and comparison only, not implemented. That's intentional, not a gap: you can't build Heap Sort's engine before you've built the engine itself.
Two sorting strategies
// The shared divide-and-conquer skeleton (same shape as Recursion Basics):
function sort(arr):
if arr is trivially small (0 or 1 elements): // base case — already sorted
return arr
... split or partition the problem ...
... recursively sort the smaller piece(s) ...
... combine the results ...Merge Sort — divide, recursively sort, merge
function mergeSort(arr):
if length(arr) <= 1:
return arr // base case: 0 or 1 elements is already sorted
mid = length(arr) // 2
left = mergeSort(arr[0:mid]) // recursively sort the left half
right = mergeSort(arr[mid:]) // recursively sort the right half
return merge(left, right)
function merge(left, right):
result = []
i, j = 0, 0
while i < length(left) and j < length(right):
if left[i] <= right[j]: // <= (not <) keeps equal elements in original
result.append(left[i]) // relative order — this is what "stable" means
i += 1
else:
result.append(right[j])
j += 1
result.append(remaining elements of left) // whichever side has leftovers
result.append(remaining elements of right)
return resultQuick Sort — pick a pivot, partition, recurse
function quickSort(arr, lo, hi):
if lo >= hi:
return // base case: 0 or 1 elements is already sorted
pivotIndex = partition(arr, lo, hi)
quickSort(arr, lo, pivotIndex - 1) // recurse left of the pivot
quickSort(arr, pivotIndex + 1, hi) // recurse right of the pivot
function partition(arr, lo, hi):
pivot = arr[hi] // pick the last element as the pivot (simplest choice)
boundary = lo // everything before 'boundary' is < pivot
for i from lo to hi - 1:
if arr[i] < pivot:
swap(arr[i], arr[boundary])
boundary += 1
swap(arr[boundary], arr[hi]) // put the pivot in its final sorted spot
return boundary"Stable" means equal elements keep their original relative order after sorting — worth caring about when you're sorting records (like people) by one field (like age) and want ties to stay in their original order.
| Operation | Time | Space | Why |
|---|---|---|---|
| Merge Sort | O(n log n) | O(n) | log n levels of splitting, O(n) work to merge at each level — but merging needs a separate output array, which is the O(n) extra space. |
| Quick Sort | O(n log n) average, O(n²) worst case | O(log n) average, O(n) worst case | Partitioning is in place (no extra array) — the space is the recursion stack, one frame per level. A consistently unlucky pivot choice can make one side of every partition empty, turning log n levels of recursion into n levels — the same pathological input that drives time to O(n²) also drives the recursion stack to O(n). |
| Heap Sort (preview — built in Phase 5) | O(n log n) | O(1) | Repeatedly pulling the current smallest/largest element from a heap costs O(log n) per pull, n pulls total — no extra array needed, but it needs a working heap first. |
Quick Sort's O(n²) worst case on sorted input
Always picking arr[hi] as the pivot on an already-sorted array means every partition puts zero elements on one side and everything else on the other — the recursion doesn't halve the problem, it only shrinks it by one each time, giving O(n) levels instead of O(log n): O(n²) total. Picking a random pivot, or the median of a few sampled elements, makes this unlucky case astronomically unlikely instead of guaranteed by a predictable input.
Merge Sort's O(n) extra space is a real cost
Merge Sort needs a second array to merge into — that's not free at scale. For huge datasets, doubling the memory footprint can matter more than the time complexity does; Quick Sort's O(log n) space (just the recursion stack) or Heap Sort's O(1) space can be the deciding factor even though all three share the same O(n log n) time.
Assuming a sort is stable when it isn't
Quick Sort's swap-based partitioning can reorder equal elements relative to each other — it's not stable by default. Code that sorts a list of records by, say, department, expecting people within the same department to stay in their original order (maybe already sorted by name), can silently scramble that secondary order if the sort used isn't stable. Check which guarantee your language's or library's sort actually makes; don't assume.
Sorting records with the wrong or an unstable comparator
A comparator that isn't consistent — for instance, one that sometimes says A < B and sometimes says B < A for the same pair, or one that doesn't handle equal elements predictably — can make different sorting algorithms produce different (and sometimes just wrong) results on the same data, since they all assume the comparator defines a single, consistent ordering to work toward.
Sign in to mark problems done — progress syncs across devices.