Foundations — Merge sort — divide and conquer, O(n log n), stable, proof of correctness

This page assumes you have seen nothing. Before you read the parent note, you should recognise every squiggle it throws at you. We build them one at a time, each on top of the one before it, each anchored to a picture.

1. A list, an array, and an index

Look at figure below: the strip has cells, and above each cell sits a small number — that number is its position, called an index. Programmers count indices starting at 0, so the first cell is index $0$, the second is index $1$, and so on.

Why does the topic need this? Every step of merge sort talks about "the front element of a list" or "the box at index $i$" — without indices we cannot point at which number we mean.

2. What "sorted" actually means

The symbol $\le$ means "less than or equal to". Why or equal and not just "less than"? Because two boxes are allowed to hold the same number and the list is still sorted — think of two cards both showing $3$ sitting side by side. That tiny "or equal" is exactly what makes the topic's stability discussion possible later.

3. Splitting: mid, //, and the floor/ceiling

The parent writes mid = len(a) // 2 and later $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$. Let us earn those.

Why do we need to drop the remainder? An index must be a whole number — there is no "box number $3.5$". So when we split a list of length $7$, the cut lands at box $3$, giving a left half of $3$ boxes and a right half of $4$.

So for length $n=7$: the left half has $\lfloor 7/2\rfloor =3$ boxes, the right half has $\lceil 7/2\rceil =4$ boxes. The two floor/ceiling brackets are just the precise way of saying "if it doesn't split evenly, the right side gets the extra box".

4. Recursion — a function that calls itself

The parent's merge_sort calls merge_sort inside itself. That is recursion.

Why does the topic need this? "Divide and conquer" is recursion — the whole speed argument depends on the problem shrinking by half each call. See Recursion and Induction for the deeper machinery; the proof of correctness on the parent page leans on it directly.

5. Two pointers i, j — fingers walking a list

The merge routine walks both lists at once with these two fingers, always comparing the two boxes the fingers rest on and taking the smaller. This picture is the merge algorithm.

6. Big-$O$, $\Theta$, and $\log$ — the size vocabulary

The parent says merge is $\Theta (n)$ and the whole sort is $\Theta (n\log n)$. Three symbols to unpack.

Why this exact tool and not another? Merge sort halves the list at every level. The natural question "how many levels of halving are there?" is precisely what a base-2 logarithm answers — that is why $\log$ (and not, say, $\sqrt{n}$) appears in the running time. The Master Theorem turns the recurrence into this $\log$ automatically.

7. The recurrence symbols $T(n)$ and the recursion tree

Why the topic needs this: the recurrence is the bridge from "the algorithm's shape" to "its running time". You solve it by drawing a recursion tree (each node splits into two half-size children), which the parent does to reach $\Theta (n\log n)$.

Prerequisite map

Equipment checklist

Test yourself — cover the right side and answer before revealing.

Connections

• Merge Sort — parent topic — everything here feeds it.
• Recursion and Induction — the self-calling machinery and the proof style.
• Big-O Notation — the meaning of $O$ and $\Theta$.
• Master Theorem — turns the recurrence $T(n)=2T(n/2)+cn$ into $\Theta (n\log n)$.
• Divide and Conquer — the paradigm merge sort belongs to.
• Stability of Sorting Algorithms — why the $\le$ tie-rule matters.