Sorting: Beyond sort()
This chapter walks through the classic sorting algorithms, their trade-offs, and when you'd pick each one.
Just Use sort()
In real code, you call list.sort() or sorted(list). Python's Timsort is O(n log n), stable, written in C, and hand-tuned for real-world data. You will almost never beat it.
So why learn sorting algorithms?
- They come up in interviews.
- Understanding how they work explains why your chosen data structure behaves as it does (e.g., why quicksort is
O(n log n)average butO(n^2)worst case). - Some real problems need custom sorts (partial sort, topological sort, specialized comparisons).
Rule: know these for interviews and intuition. Call sort() in production.
The O(n^2) Family
The first sorts everyone learns. Slow, but simple enough to implement on a whiteboard.
Bubble Sort
Repeatedly swap adjacent out-of-order pairs.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
return
O(n^2) average and worst. O(n) best (already sorted). Don't use in production.
Insertion Sort
Build the sorted portion one element at a time, inserting each into its correct place.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
O(n^2) worst, O(n) best, O(1) space. Excellent for small arrays and nearly-sorted data; Timsort uses it for small subarrays.
Selection Sort
Find the minimum, swap to front, repeat on the rest.
def selection_sort(arr):
for i in range(len(arr)):
mn = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[mn]:
mn = j
arr[i], arr[mn] = arr[mn], arr[i]
O(n^2) always. Fewer swaps than bubble sort. Pedagogical, not practical.
The O(n log n) Family
What real sorts look like.
Merge Sort
Divide into halves, sort each, merge.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:])
result.extend(b[j:])
return result
O(n log n) always. O(n) extra space. Stable (equal elements keep their relative order).
Merge sort is the safe choice when you need a guarantee. Worst case equals average case.
Quicksort
Pick a pivot, partition around it, recurse on each side.
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
O(n log n) average, O(n^2) worst (bad pivots). O(log n) space (recursion). Not stable as usually written.
In practice, quicksort is often the fastest comparison sort because its constant factors are tiny and it has great cache behavior. Production implementations (C stdlib, older JavaScript engines) use it.
Heap Sort
Build a max-heap. Repeatedly extract the max and put it at the end.
import heapq
def heap_sort(arr):
# Python's heapq is a min-heap
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]
Or in-place:
def heap_sort_in_place(arr):
n = len(arr)
def sift_down(start, end):
root = start
while 2 * root + 1 <= end:
child = 2 * root + 1
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
return
for i in range(n // 2 - 1, -1, -1):
sift_down(i, n - 1)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift_down(0, end - 1)
O(n log n) worst case. O(1) space in-place. Not stable.
Heap sort isn't the fastest, but its worst-case guarantee and O(1) space make it useful for embedded or memory-constrained environments.
Non-Comparison Sorts
The O(n log n) bound only applies to comparison-based sorts. If you can exploit structure (known range, known length), you can beat it.
Counting Sort
For integers in a known, small range.
def counting_sort(arr, max_val):
counts = [0] * (max_val + 1)
for x in arr:
counts[x] += 1
result = []
for value, count in enumerate(counts):
result.extend([value] * count)
return result
O(n + k) time and space, where k = max_val. Linear if k is small.
Useful for: histogram data, ages, scores out of 100.
Radix Sort
Sort by digits, least-significant first. Each pass is counting sort on one digit.
def radix_sort(arr):
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
counts = [0] * 10
for x in arr:
counts[(x // exp) % 10] += 1
for i in range(1, 10):
counts[i] += counts[i - 1]
result = [0] * len(arr)
for x in reversed(arr):
d = (x // exp) % 10
counts[d] -= 1
result[counts[d]] = x
return result
O(nk) where k is the number of digits. Beats O(n log n) when k is small.
Bucket Sort
Distribute into buckets, sort each, concatenate.
def bucket_sort(arr, n_buckets=10):
if not arr:
return arr
mn, mx = min(arr), max(arr)
buckets = [[] for _ in range(n_buckets)]
for x in arr:
idx = int((x - mn) / (mx - mn + 1e-9) * n_buckets)
idx = min(idx, n_buckets - 1)
buckets[idx].append(x)
result = []
for b in buckets:
result.extend(sorted(b))
return result
Good for uniformly distributed floats. Linear on average for uniform data, pathological on clustered.
Stability
A sort is stable when equal elements keep their original order. Matters when:
- You're sorting by a secondary key after sorting by a primary.
- Order of ties is semantically meaningful.
Merge sort stable
Insertion sort stable
Bubble sort stable
Timsort stable
Quicksort not (as usually written)
Heap sort not
Counting sort stable (usual implementation)
Radix sort stable (requires stable inner sort)
Python's sort() and sorted() are stable. Relied on by many production sorts of structured data.
Python's Timsort
The real-world champion. Invented by Tim Peters in 2002 for Python's sort.
- Detects already-sorted runs in the input.
- Uses insertion sort for small runs.
- Uses merge sort for longer runs, merging runs smartly.
- O(n log n) worst, O(n) best (nearly sorted data is very fast).
- Stable.
For any real Python code, just call sort(). It adapts to your data.
Custom Sorting
people = [("Ada", 36), ("Grace", 41), ("Alan", 42)]
# Sort by age
people.sort(key=lambda p: p[1])
# Sort by age descending, then name ascending
people.sort(key=lambda p: (-p[1], p[0]))
# Sort by name case-insensitively
people.sort(key=lambda p: p[0].lower())
key= is called once per element and produces the value to sort by. Much faster and cleaner than cmp= (which Python dropped anyway).
For complex comparisons that don't fit a key, use functools.cmp_to_key.
Picking a Sort
Situation Sort
Just sort it built-in (Timsort)
Need stable and O(n log n) guaranteed merge sort (or just use built-in)
Memory-constrained heap sort
Integer keys in small range counting sort
Integer keys, any size radix sort
Very nearly sorted already insertion sort (or Timsort)
Building your own stdlib introsort (quicksort → heap sort on bad pivots)
Common Pitfalls
Using bubble sort in production. Don't. Ever. Use the built-in.
Forgetting that sort is in-place. arr.sort() mutates. sorted(arr) returns a new list. Mix them up and you'll get confusing bugs.
Sorting instead of partitioning. To find the top 10, don't sort all n and take the first 10. Use a heap (O(n log 10)) or heapq.nlargest.
Writing a custom comparator in Python 3. Use key=. cmp= is gone.
Unstable sort when you needed stable. The second sort reorders what the first established. Use a stable sort or include all keys in one tuple for the key= function.
Next Steps
Continue to 07-trees.md for hierarchies and priority queues.