Sorting is the classic lens on algorithm design. Build the O(n²) sorts to see why they are slow, then merge sort and quicksort to see how divide-and-conquer reaches O(n log n) — and when to just call sorted().
Sorting is worth studying both because it is ubiquitous — sorted data unlocks binary search, deduplication, and many greedy algorithms — and because it teaches algorithm design in miniature. One property to know: a stable sort preserves the relative order of equal elements, which matters when sorting by multiple keys. Comparison sorts cannot beat O(n log n) in the general case.
Why learn sorting:
- sorted data enables binary search, dedup, many greedy algorithms
- it's the clearest case study in algorithm design (brute force -> clever)
Key ideas:
STABILITY equal elements keep their original order after sorting
(needed for multi-key sorts: sort by name, then by age)
LOWER BOUND comparison-based sorting can't beat O(n log n) in general
The families:
O(n^2) bubble, insertion, selection — simple, slow, teachable
O(n log n) merge, quicksort, heapsort — what you actually useBubble, insertion, and selection sort all use nested loops and run in O(n²). They are too slow for large inputs but worth building once to feel why. Insertion sort is the useful one: it is simple, stable, and genuinely fast on small or nearly-sorted data, which is why real library sorts fall back to it for tiny subarrays.
# insertion sort: grow a sorted prefix, insert each new element into place
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key: # shift bigger elements right
a[j+1] = a[j]
j -= 1
a[j+1] = key
return a
# O(n^2) worst case, but O(n) on nearly-sorted data + stable + simple.
# selection sort: repeatedly pick the smallest remaining — always O(n^2)
def selection_sort(a):
for i in range(len(a)):
m = min(range(i, len(a)), key=lambda k: a[k])
a[i], a[m] = a[m], a[i]
return aMerge sort splits the array in half, sorts each half recursively, then merges the two sorted halves in linear time. The halving gives log n levels and each level does O(n) merging work, for O(n log n) overall. It is stable and has predictable performance, at the cost of O(n) extra space — the archetype of divide-and-conquer.
def merge_sort(a):
if len(a) <= 1: # base case
return a
mid = len(a) // 2
left = merge_sort(a[:mid]) # sort each half (log n levels)
right = merge_sort(a[mid:])
return merge(left, right) # combine in O(n)
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps it STABLE
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]); out.extend(right[j:])
return out
# O(n log n) time, O(n) space, stable, predictable.Quicksort picks a pivot, partitions the array so smaller elements go left and larger go right, then recurses on each side. It sorts in place with O(n log n) average time and is very fast in practice, but a bad pivot on already-sorted data degrades to O(n²) — mitigated by choosing the pivot randomly. It trades merge sort’s stability and predictability for lower memory use.
import random
def quicksort(a):
if len(a) <= 1:
return a
pivot = random.choice(a) # random pivot avoids O(n^2) on sorted input
less = [x for x in a if x < pivot]
equal = [x for x in a if x == pivot]
greater = [x for x in a if x > pivot]
return quicksort(less) + equal + quicksort(greater)
# average O(n log n); worst case O(n^2) with a bad pivot (random pivot avoids it).
# real in-place quicksort partitions within the array to use O(log n) space.You should understand these algorithms, but in real code you call the language’s sort — Python’s sorted()/list.sort() uses Timsort, a highly optimized, stable hybrid of merge and insertion sort that is O(n log n) and exploits existing order. The real skill is knowing sorting’s cost and how to sort by custom keys, not reimplementing it.
# Timsort (Python's built-in): stable, O(n log n), adaptive to existing order
sorted([3, 1, 2]) # [1, 2, 3] (returns a new list)
nums = [3, 1, 2]; nums.sort() # sorts in place
# sort by a custom key — the part you actually use daily
people = [("Ann", 30), ("Bo", 25), ("Cy", 30)]
sorted(people, key=lambda p: p[1]) # by age
sorted(people, key=lambda p: (-p[1], p[0])) # age desc, then name asc
# know the COST (O(n log n)) and how to key it. Don't hand-roll sorts in prod.