In the previous lesson, all the magic of binary search rested on one premise: the data was already sorted. This lesson pays that debt. Rutalia generates hundreds of thousands of delivery records every day — millions per month — and needs them sorted by (zone, time) to consolidate routes, by postal code to palletize, by weight to price. At that scale, the difference between an O(n²) algorithm and an O(n log n) one is not "a bit slower": it is the difference between 3 seconds and several days. Here we will study mergesort and quicksort (the two great divide-and-conquer algorithms), heapsort (cashing in the heap we built in 01-04), the Ω(n log n) lower bound that no comparison-based algorithm can beat, the non-comparison sorts that do beat it (counting sort and radix sort), and finally Timsort: what Python actually runs when you call sorted, and how to get the most out of it with key= and stability.

1. Why O(n²) doesn't work at scale
2. Mergesort: divide and conquer with guarantees
3. Quicksort: partition, pivot and the worst case
4. Heapsort in brief: the heap from 01-04 put to work sorting
5. The Ω(n log n) lower bound: the decision tree
6. Sorting without comparing: counting sort and radix sort
7. Timsort: what Python really uses (sorted, key=, stability)
8. Final comparison table

In 01-01 we drew the growth hierarchy: log n ≪ n ≪ n log n ≪ n². Let's put Rutalia numbers on it. Assume ~10⁸ elementary operations per second (a reasonable order of magnitude for Python with small constants):

The quadratic algorithms (bubble, selection, insertion) are not "bad": insertion sort is in fact excellent for small n or nearly sorted data, and we will see that Timsort uses it internally. But as the main algorithm at the scale of Rutalia's data they are ruled out. We need n log n, and there are three classic roads to get there: split down the middle (mergesort), split around a pivot (quicksort) and use a data structure (heapsort).

The strategy is the same one we used in 01-03 with recursion: solve two halves and combine. The key operation is the merge: given two already sorted lists, produce a sorted one in O(n) by always comparing the heads.

Three observations that matter:

• Cost. The recurrence is T(n) = 2·T(n/2) + O(n): two half-size subproblems plus a linear merge. By the master theorem from 01-02 (case 2: the work is split evenly across levels), T(n) = Θ(n log n) — and this holds always: best case, worst case and average case. Mergesort has no surprises.
• Stability. The <= in the merge means that, on a tie, the element from the left half wins — that is, the one that came first in the original list. Two deliveries with the same minute (9) keep their relative order (E-013 before E-088). Hold on to this concept: it will be the centerpiece of the Timsort section.
• Memory. This version creates new lists at every level: O(n) auxiliary memory. A nearly in-place mergesort exists, but it is complex and rarely worth it; accepting the extra O(n) is the standard price. When not even one copy fits in RAM (years of history), the merge is done in blocks from disk — that is external sorting, which we will develop in 06-03.

Quicksort also divides, but the opposite way round from mergesort: the work happens before recursing, in the partition. A pivot element is chosen and the array is rearranged into three zones: less than, equal to and greater than the pivot. Then the less-than and greater-than zones are sorted recursively — and there is nothing to combine, because the partition already left every element on the correct side.

First, the pedagogical version (clear but with extra memory):

And the in-place version that gives quicksort its fame (Lomuto partition, the easiest to reason about):

The partition invariant (invariants again, as in 04-01): at the end of each loop iteration, a[lo..i] contains only elements <= pivot and a[i+1..j] only elements > pivot.

If the pivot splits the array into similar halves, the recurrence is mergesort's: Θ(n log n). But if the pivot is always the minimum or the maximum, one "half" has n−1 elements: T(n) = T(n−1) + O(n) = O(n²). And when does that happen with the naive "first element" pivot? With data that is already sorted or nearly sorted — exactly the most common case in practice (Rutalia's history arrives nearly sorted by timestamp, with the odd out-of-order correction). A naive quicksort gets worse the easier the input looks.

Mitigations, from simplest to most robust:

Two further notes: recursion depth is also O(n) in the worst case (in Python, a RecursionError; mitigated by recursing only on the small part and iterating over the large one), and the swap-based partition is not stable — two tied deliveries can end up in the reverse of their original order. In exchange, quicksort sorts in place (O(log n) of stack, no auxiliary array) and its constants are excellent thanks to its good cache behavior: that is why, well implemented, it usually beats mergesort in practice.

In 01-04 we built min-heaps with heapq for the priority delivery queue, and in 02-03 and 03-03 we reused them for best-first search and for Dijkstra. Heapsort is the observation that a heap already is a sorting algorithm: build a heap with the n elements (O(n) with heapify) and extract the minimum n times (n × O(log n)).

The balance sheet: O(n log n) guaranteed (like mergesort), in-place in its classic array version (the one above uses a copy for clarity), but not stable and with worse constants than quicksort (the jumps through the heap's tree punish the cache). Its modern role is that of a safety net: it is introsort's plan B when quicksort degenerates. We won't give it more space because you already mastered the heap mechanics in module 1.

We have three O(n log n) algorithms. The natural question: can we go lower? For algorithms that gain information only by comparing pairs of elements, the answer is no, and the argument is beautiful and intuitive:

1. A comparison-based sorting algorithm is, seen from the outside, a decision tree: each internal node is a question "a[i] < a[j]?" with two branches (yes/no), and each leaf is a final result — a specific permutation of the input.
2. With n distinct elements there are n! possible permutations, and the algorithm must be able to produce any of them: the tree needs at least n! leaves (if two distinct permutations reached the same leaf, the algorithm would be wrong on at least one).
3. A binary tree of depth d has at most 2^d leaves. We need 2^d ≥ n!, that is d ≥ log₂(n!).
4. By Stirling's approximation, log₂(n!) ≈ n·log₂ n − 1.44·n = Ω(n log n).

The tree's depth is the number of comparisons in the worst case. Conclusion: no comparison-based algorithm, however ingenious, goes below Ω(n log n) in the worst case. Mergesort and heapsort are, in this sense, optimal. It is the same kind of "impossibility" result as the practical NP-hardness of 02-02, but much stronger: here it is proven unconditionally.

The fine print is the door to the next section: the bound only applies to algorithms that compare. If we know something more about the keys, we can cheat legally.

If the keys are integers in a small range [0, k), no comparisons are needed at all: you count how many times each key appears and reconstruct the output. Rutalia example: sorting the day's deliveries by zone (9 zones: the urban network from module 3).

Cost O(n + k): linear if k = O(n). With n = 1,000,000 deliveries and k = 9 zones, it is unbeatable. The applicability condition is harsh: integer keys (or keys mappable to integers) in a small range k. Sorting by amount in cents up to 10,000 EUR (k = 10⁶) is still fine; sorting by nanosecond timestamp is not.

And what if the range is large but the keys have digits? Radix sort (LSD, least significant digit) sorts by the least significant digit, then by the next one, and so on, using a stable sort (counting sort) on every pass. Stability is what keeps earlier passes from being destroyed: when sorting by the second digit, ties preserve the order by the first.

Rutalia's canonical example: palletizing by 5-digit postal code.

Cost O(d · (n + b)) with d digits in base b. For postal codes, d = 5 and b = 10: linear in n with a constant of 5. The same idea sorts 64-bit integers in 8 passes of base 256 — that is how many high-performance libraries sort numeric keys. The Ω(n log n) bound is not violated: we are not comparing, we are exploiting the structure of the key.

When you write sorted(deliveries) or deliveries.sort(), Python does not run any of the previous textbook algorithms in pure form: it runs Timsort (created by Tim Peters for CPython in 2002; later adopted by Java for objects and by many other languages). Timsort is a mergesort + insertion hybrid designed for real data, not random data:

• It detects runs: stretches that are already sorted (ascending, or descending, which it reverses). Rutalia's history arrives nearly sorted by timestamp: Timsort detects those huge stretches and merely merges them. On already sorted data it is O(n).
• Insertion sort for short stretches: runs shorter than ~32 elements are extended with insertion sort — the O(n²) algorithm we discarded, unbeatable at tiny n.
• Smart merges: it stacks the runs and merges them with rules that balance sizes, using galloping to skip over blocks when one half dominates.
• Guarantees: O(n log n) in the worst case, O(n) in the best, and — crucially — stable.

The engineering moral: in Python, do not reimplement quicksort for production. sorted is written in C, adaptive and stable; your pure-Python quicksort will be tens of times slower. The algorithms in this lesson are studied to understand costs, guarantees and when a specialized sort (counting/radix, external sorting) beats the generic one — not to replace sorted.

What you will use daily is the interface. key= takes a function that extracts the key from each element (it is called once per element, not on every comparison):

Option B is exactly the radix sort trick at user level: since sorted is stable, the second sort does not undo the ties left by the first. It is the essential technique when the secondary criterion cannot be negated (descending strings, for example). And it is the reason why stability, which looked like a technicality in mergesort, is a first-class property in practice.

• Reimplementing sorting for production. The number-one mistake. sorted (Timsort in C) beats any implementation of yours in pure Python. Implement to learn; deploy the library.
• Quicksort with a fixed pivot on nearly sorted data. The O(n²) worst case is not theoretical: it shows up precisely with the most common input. Random pivot or median of three, always.
• Assuming every sort is stable. Python's sorted is; quicksort and heapsort are not; neither is numpy.sort by default (quicksort). If you chain criteria with successive sorts, verify the stability of the algorithm you use or the result will be subtly wrong.
• key= with expensive work recomputed. key is evaluated once per element, which is already optimal — but if the key requires parsing a date or looking up a dict, pull that computation out if you will sort several times (the decorate-sort-undecorate pattern if needed).
• Using counting sort with a huge k. O(n + k) is linear only if k = O(n). With 64-bit keys, the counting array does not fit in the memory of any Rutalia server. For large ranges with digit structure: radix sort.
• Comparing with a mental cmp instead of keys. In Python 3 the cmp parameter does not exist; always think "which key tuple represents my criterion?" — almost any compound criterion can be expressed as a tuple, with negations to reverse numeric fields.
• Tip: for data that "arrives nearly sorted with exceptions" (Rutalia's history after manual corrections), measure before optimizing: Timsort is already close to O(n) in that case, and you may not need anything else.

Exercise 1 — Route consolidation. Given a list of deliveries (id, zone, time, weight) (tuples), produce Rutalia's work order: by zone in ascending alphabetical order, within each zone by time ascending, and when both are equal, the heaviest package first. Solve it two ways: (a) with a single call to sorted and a key tuple; (b) with successive sorts exploiting stability. Check that they match.

Exercise 2 — Which algorithm would you choose? For each Rutalia scenario, pick the most suitable algorithm from the comparison table and justify it in one sentence: (a) sorting 5,000,000 packages by 5-digit postal code; (b) sorting a van's 40 stops by promised time, on a microcontroller with minimal memory; (c) sorting the monthly history by timestamp knowing it arrives 99% sorted with some corrections interleaved; (d) sorting 2,000,000 deliveries by zone (9 values) while preserving arrival order within each zone.

Exercise 3 — Merging k routes (bridge to 01-04). Each of Rutalia's k vans returns its daily log already sorted by time. Write merge_k(lists) producing the global sorted log in O(N log k), where N is the total number of records — use a heap with tuples (time, list_index, element_index) as in 01-04. Why is this better than concatenating and calling sorted? (Hint: think about the best case and about memory; note also that this k-way merge is the heart of the external sorting of 06-03.)

Solution 1:

The detail to internalize in (b): the order of the passes is the reverse of the criteria's priority, and it works only because sorted is stable — each pass respects the ties left by the previous ones.

Solution 2:

• (a) LSD radix sort with stable counting sort per digit: 5 O(n) passes, well below n log n for n = 5·10⁶. (In practice, benchmark against sorted: the constant of compiled C sometimes wins anyway.)
• (b) Heapsort (or insertion — at n = 40 it hardly matters): O(n log n) guaranteed with O(1) extra memory; no mergesort auxiliary array and no quicksort O(n²) risk.
• (c) Timsort (sorted as is): its run detection makes it nearly O(n) on nearly sorted data; any further effort is premature.
• (d) Counting sort by zone index (k = 9): O(n + 9), linear and stable, which is exactly the "preserve arrival order within each zone" requirement.

Solution 3:

Advantages over sorted(concatenation): (1) cost O(N log k) versus O(N log N) — with k = 20 vans and N = 10⁶, log k ≈ 4.3 versus log N ≈ 20; (2) it is a streaming algorithm: it can emit results without holding the k full lists in memory if they arrive as streams, which is exactly what the block merge of external sorting needs (06-03). It already exists in the standard library: heapq.merge(*lists).

You now have the complete map of sorting: the quadratic algorithms die at scale (though insertion survives as an internal component), mergesort and heapsort guarantee the n log n that quicksort only promises on average (and that introsort turns into a guarantee by combining them), and the decision-tree bound Ω(n log n) proves that by comparison you cannot do better — but counting sort and radix sort dodge it legally when the key has structure, like postal codes or Rutalia's 9 zones. And in everyday Python, the answer is almost always sorted with a good key tuple, leaning on Timsort's stability to compose criteria. When volumes overflow RAM and sorting has to happen on disk or across machines, the k-way merge from the last exercise will be the key piece — we will see it in 06-03.

With searching (04-01) and sorting (04-02) mastered over static data, one third kind of search remains, the most ambitious: searching not for a value in an array, but for a solution in a universe of possibilities — the delivery route around obstacles, the sequence of moves that leads from the initial state to the goal. In the next lesson (04-03) we formalize state spaces, meet BFS, DFS and Dijkstra again in their implicit versions, and finally deliver on module 3's promise: A*, "Dijkstra with a compass".