Insertion sort (04-02) hits a ceiling at Θ(n²) because it moves elements one at a time. To break that barrier we will apply, at last in its pure form, the strategy from 03-01: merge sort is the direct child of divide and conquer — split the list into two halves, sort them recursively, and merge them. All of its ingenuity lives in that merging: combining two already sorted lists into one costs only O(n). In this lesson we will first build the merge function, then the complete algorithm, trace it over eight RutaBus arrivals with the tree of splitting and merging, and settle the oldest debt of the course: rigorously solving the recurrence T(n) = 2·T(n/2) + O(n) we jotted down in 03-01. We will close with its costs (stable, but not in-place) and its real-world uses, from sorting gigantic files to Python's Timsort.

1. The idea: the work happens when combining
2. The merge function: two pointers over two sorted lists
3. Complete merge sort implementation
4. Trace: the splitting-and-merging tree with 8 arrivals
5. The recurrence T(n) = 2·T(n/2) + O(n), solved by levels
6. Stability and space cost: the price of O(n log n)
7. Merge sort in the real world: external sorting and Timsort

Recall the scheme from 03-01 — divide, conquer, combine — and apply it to sorting:

1. Divide: split the list into two halves (trivial: one cut through the middle).
2. Conquer: sort each half recursively with merge sort itself. Base case: a list of 0 or 1 elements is already sorted.
3. Combine: merge the two sorted halves into a single sorted list.

Notice where the intelligence lives: dividing is a dumb cut and conquering is delegating to the recursion. All the substance is in step 3. This distribution of effort — cheap dividing, laborious combining — is merge sort's signature; in the next lesson we will see its exact mirror image (quicksort: laborious dividing, free combining).

Why can this beat insertion sort? Because merging two sorted lists of size n/2 does not require comparing everything against everything: since both are already sorted, a single simultaneous sweep is enough. That "a single sweep is enough" is the gold mine.

The auxiliary problem: given two already sorted lists, produce a sorted list with all their elements. The technique is called two pointers: one index per list, and at each step the smaller of the two candidates is copied.

Think of two piles of tap records from L1 and L2, each already sorted by time, that must be fused into a single listing: you look at the top card of each pile, move the earlier one to the listing, and repeat.

Point by point:

• The two pointers only move forward: i walks through left and j walks through right, each from left to right, never backing up. Each comparison copies exactly one element to the result, so the loop runs at most len(left) + len(right) times: merge is O(n) in the total number of elements. Invariant: result contains, in order, all the elements already consumed, and everything still pending is ≥ the last one copied.
• <= instead of <: on a tie we copy first the one from the left list — the one that came earlier in the original list. That way ties keep their relative order: it is the detail that will make the full merge sort stable, just as the strict > did for insertion sort (04-02).
• The leftovers (extend): when one list runs out, the other may have a tail pending; since it is sorted and all its elements are larger than everything already copied, it is appended in one block.

A direct example with two sorted boards:

With merge solved, the complete algorithm is short — divide and conquer in its purest state, compare it with the template from 03-01:

• The base case cuts the recursion off at lists of size ≤ 1, which are sorted by definition. Without it, items[:0] and the calls would go on forever — the classic mistake from 03-01.
• The cuts items[:middle] and items[middle:] copy the sublists (Python's hidden cost, 02-01). It is convenient but contributes to the space cost we will analyze in section 6.
• Unlike insertion_sort, this version returns a new list instead of modifying the original: functional style, easier to reason about.

Let's sort the 8 accumulated arrivals on the North Station board:

The process draws two pyramids: one of splitting (downward) and one of merging (upward):

Reading the tree:

• Going down (splitting): 8 → 4+4 → 2+2+2+2 → eight leaves of 1 element. With n = 8 = 2³ there are exactly 3 levels of splitting: log₂ 8, the level counting from 03-01.
• Going up (merging): the leaves merge in pairs. Follow one: merge(["18:42"], ["18:07"]) → ["18:07", "18:42"]. Then merge(["18:07","18:42"], ["18:31","18:59"]) → ["18:07","18:31","18:42","18:59"]: the pointers keep jumping between lists (18:07 from left, 18:31 from right, 18:42 from left...). The final merge interleaves two halves of 4.
• Each merge level touches all 8 elements exactly once: 4 merges of 2, then 2 merges of 4, then 1 merge of 8 — always 8 copies per level. Hold on to this fact: it is the key to the analysis.

In 03-01 we wrote down the recurrence and promised to solve it here. Merge sort embodies it literally:

Levels method (the one from 03-01, now with all the arithmetic). We unfold the call tree and add up the non-recursive work (the merging) level by level:

The pattern we saw in the trace is general: every level costs exactly c·n, because going down one level doubles the subproblems but halves their size — the product does not change. And the number of levels is the number of times n can be halved: log₂ n (04-01 called it "counting halves").

Debt settled. And with a bonus: in merge sort this cost does not depend on the input. The merge always sweeps both lists in full, whether the board is already sorted, reversed, or random:

That bottom-left corner is the unconditional guarantee that worst-case analysis (02-03) taught us to value: merge sort is as predictable as a clock. The price: it does not exploit nearly sorted data the way insertion sort does (its best case is also n log n).

To calibrate the victory: with n = 10,000 runs, insertion sort averages ≈ n²/4 = 25,000,000 operations; merge sort, ≈ n·log₂ n ≈ 132,000. Almost 200 times fewer.

Stability: yes. The <= in merge guarantees that on a tie the element from the left half — the one that came earlier in the original list — is copied first. Since this holds in every merge at every level, the relative order of ties survives to the end. Merge sort sorts a board of (time, line) tuples by time without scrambling the ties (the example from 04-02).

Space: O(n) auxiliary — it is not in-place. Every merge builds a new result list, and the cuts items[:middle] copy. With the analysis from 02-02: at the moment of the final merge, the input and the result coexist — Θ(n) of extra memory — plus the O(log n) frames of the recursion stack (dominated by the previous n). Compare with insertion sort's O(1):

It is the time ↔ space trade-off from 02-02 in its textbook version: merge sort buys guaranteed speed by paying memory. (In-place variants of merge sort exist, but they are notoriously intricate and rare in practice; the usual answer to "I want n log n without extra memory" is a different one: quicksort, in the next lesson.)

External sorting. Picture RutaBus's yearly history of tap records: 500 GB that do not fit in the server's 32 GB of RAM. Merge sort is the only one of our algorithms comfortable working like this, because merge only needs to read the lists sequentially, start to finish:

1. Read the file in blocks that do fit in RAM, sort each block (with whatever you like) and write it to disk: you get many sorted runs.
2. Merge the runs by reading them in parallel with the pointer technique — each file is read sequentially, which is exactly what disks do fast — until only one remains.

This scheme (external merge sort) is the foundation of how databases and big data frameworks sort when the data does not fit in memory.

Timsort: the circle closes. Python's sorted() and list.sort() use Timsort, a hybrid designed in 2002 for Python itself that combines... our last two lessons:

• It detects runs: already sorted stretches present in real data (the nearly sorted boards from 04-02), and extends them with insertion sort — exploiting the fact that on short, nearly sorted stretches it is unbeatable.
• It merges the runs with a fine-tuned merge, preserving stability and the O(n log n) worst-case guarantee.

Result: O(n) on already sorted data (inherited from insertion sort), O(n log n) guaranteed (inherited from merge), and stable. When back in 02-01 we took for granted that sorted cost O(n log n), this is what was underneath. Engineering moral: the "textbook" algorithms do not compete with each other, they combine — each covering the other's weak spot.

• Forgetting the base case (len(items) <= 1): the recursion never ends (RecursionError). It is the first thing to check in any divide and conquer, as we already warned in 03-01.
• Forgetting the leftovers in merge: without the final extend calls, the elements of the non-exhausted list are lost. Symptom: the result comes out sorted... but shorter than the input. Always check len(result) == len(left) + len(right).
• Using < instead of <= in merge: it still sorts fine, but on ties it copies the right-hand element first and breaks stability — the same silent mistake as the >= in insertion sort. Only a test with duplicate keys detects it.
• Miscomputing middle (len(items) / 2 with / returns a float and breaks the slicing; or splitting into [:middle+1] and [middle:] duplicates the central element). The correct cut is exhaustive and disjoint: [:middle] and [middle:].
• Debugging tip: print the list at every return of merge_sort with indentation proportional to the depth. You will see the tree from section 4 draw itself, and you will pinpoint in which merge the result went wrong.

Trace merge(["18:03", "18:31", "18:44"], ["18:03", "18:12"]) step by step: a table with i, j, comparison, element copied. The two "18:03" entries come from different lines (the one in the first list came earlier on the original board): check that stability is respected and point out the exact comparison where the <= makes the difference.

How many merge levels does merge sort have with n = 1,024 arrivals? And how many element copies are made in total (approximately)? With those figures, explain in one sentence why doubling n (1,024 → 2,048) barely doubles the total time, while in insertion sort it would quadruple it.

Write merge_k(lists) that merges k already sorted boards (one per RutaBus line) into a single sorted listing, merging them two at a time, tournament-style: merge the boards in pairs, then the pairs of results, and so on. Reason about its complexity as a function of n (total number of elements) and k. Hint: it is the same levels argument as in section 5.

Solution 1

Result: ["18:03", "18:03", "18:12", "18:31", "18:44"]. The comparison at step 1 is the decisive one: with <=, the tie goes to the left (the element that came earlier on the original board) and stability is preserved; with < the right-hand one would have been copied first, inverting the ties.

Solution 2

1,024 = 2¹⁰ → 10 levels of merging. Each level copies the 1,024 elements once → ≈ 10 × 1,024 = 10,240 copies (plus the comparisons, of the same order). Doubling to n = 2,048 gives 11 levels × 2,048 ≈ 22,500: barely 2.2×. In insertion sort the average cost n²/4 goes from ≈ 262,000 to ≈ 1,048,000: 4×. It is the difference between growing like n log n (the log factor barely moves) and like n² (doubling the input quadruples the work) — the hierarchy from 01-03 in concrete numbers.

Solution 3

Levels analysis: each round merges every element once → O(n) per round; the number of boards halves with each round → log₂ k rounds. Total: O(n log k). It is the same levels theorem as in section 5 with k playing the role of n. The naive alternative (merge board 1 with board 2, the result with board 3, and so on) sweeps the first elements over and over: O(n·k) — tournament merging is to chain merging what merge sort is to insertion sort.

Merge sort is divide and conquer in its purest state: cut through the middle, sort recursively, and merge with two pointers in O(n). We have settled the recurrence pending since 03-01 — T(n) = 2·T(n/2) + O(n) = Θ(n log n), because each of the log n levels costs exactly n — and we have seen that this bound holds always: best, worst and average, the unconditional guarantee insertion sort could not give. In exchange it pays O(n) of auxiliary memory — the time ↔ space trade-off from 02-02 — and gives up exploiting small disorder, although Timsort proves that insertion and merging make a wonderful alliance, and external sorting crowns it as the algorithm for data that does not fit in memory. One question remains open: can you have O(n log n) without paying the extra memory? The answer is the most famous — and most treacherous — algorithm of them all: quicksort, where the work happens not when combining but when dividing, and where we will finally collect on the promise from 02-03 about the gap between the average case and the worst case.