Sorting — knowing what Python actually does

When you call sorted() or list.sort() in Python, you're invoking timsort — an algorithm specifically designed for real-world data. Three properties matter.

O(n log n) worst case. Same as mergesort, heapsort, quicksort (on average). Asymptotically optimal for comparison-based sorting.

O(n) on already-sorted or nearly-sorted data. This is timsort's special skill. Real data often has runs of already-sorted segments — timsort detects them and merges efficiently. On an already-sorted list, it's literally linear time.

Stable. Equal keys retain their original relative order. This matters more than people realise.

Why stability matters. Suppose you have a list of (city, score) pairs, and you want to sort first by city, then within each city by score descending.

With stable sort — sort by score (descending) first. Then sort by city. Within each city, the original order (which is now score-descending) is preserved. Done in two passes.

With unstable sort — second sort might disturb the score order within a city. You'd need a tuple key to do both at once, which is more code.

Python guarantees timsort stability. Most other languages don't — C++ std::sort is unstable; you have to ask for std::stable_sort. Java's Arrays.sort on objects is stable; on primitives it's not. Knowing your language's default matters.

A related guarantee — timsort is 'natural'. Reverse-sorted data is also fast (it detects descending runs and reverses them). Mostly-sorted with a few out-of-place elements is fast.

For your code — sorted() and list.sort() are almost always the right answer. The few cases they're not: when you only need top-k (use heapq), when you need to maintain a sorted collection across many inserts (use sortedcontainers), when stability would actively bite you (rare, but exists in some specialised algorithms).

Know what your sort does.

Python's sorted() and list.sort() take a key= argument. The key is a function called once per element, producing the sort key for that element. Python sorts by the keys, not by the original elements.

sorted(students, key=lambda s: s.score)

This sorts students by their score attribute. The lambda is called once per student; Python uses the resulting numbers to order the list.

Key functions enable arbitrary sort orders without writing comparator functions (which Python doesn't really support — cmp_to_key exists but is rarely the right tool).

Common patterns:

Sort by an attribute — key=lambda s: s.score, or key=operator.attrgetter('score') for a slight speed bump.

Sort case-insensitively — key=str.lower. Each string is lowercased once for sort comparison; the original strings are returned.

Sort by multiple keys — key=lambda s: (s.team, -s.score). Tuple comparison is lexicographic. First sort by team, ties broken by score descending. The negation flips the sort direction for that key only.

Sort by a complex computation — key=lambda x: complex_function(x). The function is called n times total (not n*log n), so even slow keys are tolerable.

Reverse sort — sorted(items, reverse=True). Or, equivalently, key=lambda x: -x for numeric keys.

Descending on one key, ascending on another — tuple key with negation on the descending one.

What NOT to do — chain multiple .sort() calls expecting the second to refine the first. It works (because timsort is stable) but it's slower than a single tuple-key sort.

The key= parameter plus tuple keys covers 99% of real sorts you'll write. Reach for cmp_to_key only for genuinely non-key-shaped comparisons (rare).

Need the top 10 of a billion items? Don't sort the billion.

Full sort is O(n log n). For n = 10^9, that's 30 billion ops. Even if each op takes a nanosecond, you're at 30 seconds. And you need to hold the entire billion in memory.

A min-heap of size k gives you top-k in O(n log k). For k = 10, log k = 3.3. For n = 10^9, total work is ~3.3 billion ops. Ten times faster, and memory is bounded by k, not n.

Python's heapq makes this easy.

import heapq

top10 = heapq.nlargest(10, items, key=lambda x: x.score)

One function call. heapq.nlargest maintains a min-heap of size k as it walks the iterable, kicking out the smallest item when a larger one comes in. At the end, the heap contains the top-k. It returns them sorted (largest first).

For streaming data — items arriving one at a time, you can't materialise the full list — use the heap directly:

heap = []
for item in stream:
    if len(heap) < k:
        heapq.heappush(heap, (item.score, item))
    else:
        heapq.heappushpop(heap, (item.score, item))

heappushpop pushes a new item AND pops the smallest, in one operation. Slightly more efficient than push-then-pop. The heap stays at size k.

When this matters — recommendation systems (top-k similar items), search ranking (top-k results), trending topics (top-k counts), top-K loss in classification. Anywhere you need top elements without the full sort.

Also — heapq.nsmallest for the inverse problem. heapq.merge for streaming-merge of multiple sorted iterables. Smaller features, same module, all standard library.

When full-sort is overkill, heapq is the tool.

Common pattern that's slower than it should be — sort the array, take the middle element, return as median.

O(n log n). Wasteful when you only need ONE statistic from the data.

Better approach — quickselect. O(n) average. Selects the k-th smallest element by partitioning, like quicksort but only recursing into the side containing k. Median is k = n/2.

In Python, you don't write quickselect by hand. Use:

import statistics
statistics.median(data)

statistics.median uses an efficient algorithm under the hood. Same with statistics.quantiles for arbitrary percentiles.

For really large data — t-digest sketches give approximate quantiles in O(n) time and bounded memory, even for streaming data. Libraries: datasketch (Python), tdigest (Python), or use tools like Apache Druid that have it built in.

The broader principle — don't compute more than you need. Sorting an array materialises the entire ordering. If you only need the median, the top-k, the count of elements > threshold, or any other partial statistic, there's almost always a faster algorithm.

Examples:

Min / max — O(n) with builtin min() / max(). Don't sort first.

Top-k — O(n log k) with heapq. Don't sort first.

Median — O(n) with statistics.median. Don't sort first.

Count of elements satisfying a predicate — O(n) with sum(1 for x in data if pred(x)). Don't sort first.

Is every element distinct — O(n) with len(set(data)) == len(data). Don't sort first.

The 'don't compute more than you need' principle saves more time in real Python code than algorithmic optimisations on the actual computation. Lazy when you can; full-compute only when you must.

End of Day 24. Sorting and selection done.

What we covered.

Morning, Python's sort is stable timsort. O(n log n) worst case, O(n) on already-sorted data. Stability lets you do multi-pass sorts where each later pass refines the previous.

Midday, the key= parameter and tuple keys for arbitrary sort orders. Sort by attribute, sort case-insensitively, sort by multiple keys with mixed directions. Covers 99% of real sorts.

Afternoon, heapq for top-k. O(n log k) instead of O(n log n). Saves dramatic time and memory when k is small relative to n. heapq.nlargest is the easy interface; the streaming heap pattern handles online data.

Evening, the broader principle — don't compute more than you need. statistics.median for medians. min/max for extremes. set membership for distinctness. Sorting is overkill for one-stat queries.

A pattern across the day. Many algorithmic 'wins' come from picking the right tool for the actual question. If the question is 'find the median', the sort algorithm doesn't matter — the right algorithm is quickselect or median-of-medians, which is linear. If the question is 'find top-k', the right tool is a heap, not a sort. Recognising the question is half the optimisation.

Tomorrow, Day 25, trees. BFS, DFS, and the structure that ML loves (decision trees, parse trees, abstract syntax trees, file systems). The DFS recursive vs iterative tradeoff. Plus a bonus introduction to tries — the structure for fast prefix matching.

See you in the morning.