The deterministic Huffman code is prefix-optimal

If $m=1$, the algorithm returns $0$ by [F7]. Every codeword is nonempty by [F3], so every one-symbol code has expected length at least $1$; the returned code is prefix-free by [F2] and attains that value.

Suppose $m\ge 2$. Every merge removes two nodes and adds one, so the active count decreases by exactly one; after $m-1$ merges there is one root. Each original symbol remains one leaf, and the only new nodes are internal parents by [F6]. Distinct leaves cannot lie on one root-to-leaf path, so their path words are distinct and neither is a prefix of another. Every path has positive length because the root is internal. Thus [F2] gives a binary prefix code.

An optimal prefix code exists. For every integer $m\ge 1$, $m\le 2^m$ by induction: it holds at $m=1$, and $2^{m+1}\ge 2m\ge m+1$. Thus [F4] applied to the length list $(m,\dots ,m)$ gives a finite prefix code, since its Kraft sum $m{2}^{-m}\le 1$; let its cost be $L_0$. Any code with cost at most $L_0$ has $1\le {\mathrm{\ell }}_i\le L_0\mathrm{/}{p}_i$ for every $i$, because $p_i>0$ and all summands in $L_p$ are nonnegative. Only finitely many positive integer length vectors satisfy these bounds, and at least one is realized. A least cost among those realized vectors exists and is a global minimum because every code outside the set has cost greater than $L_0$.

For an active list of size two and total weight one, the algorithm merges its two nodes into a root with two leaves, giving lengths $1,1$ and cost $1$. Every binary source code has nonempty words by [F3], so every competing prefix code has both lengths at least one and cost at least the sum of the weights, namely $1$ by [F1]. Thus the size-two case is optimal.

Suppose the active list has size $m\ge 3$ and assume as induction hypothesis that every sequence of minimum-weight merges on a positive normalized list of size $m-1$ with distinct serials gives an optimal code.

In an optimal code tree, no internal vertex has exactly one child: contracting its sole edge preserves the leaves and their incomparability, so [F2] still gives a prefix code, while every codeword below the vertex loses one bit. At least one symbol is below it by the trie definition, and its positive weight by [F1] makes the expected length strictly smaller, a contradiction. Hence every internal vertex has two children. Choose a leaf of maximal depth $d$. Its sibling cannot be internal, since that sibling would have a descendant leaf deeper than $d$; it is therefore another leaf at depth $d$.

The first selected pair $a,b$ gives a reduced list of size $m-1$ with positive weights summing to one and distinct serials. Its subsequent merges are minimum-weight choices by [F5] and [F6]. The induction hypothesis in step 1.5 therefore makes the reduced tree optimal for its weights.

Let $a,b$ be the two symbols selected by the algorithm for its first merge; [F5] and [F6] make them two symbols of least weight. Place them at a sibling pair of leaves at depth $d$ without increasing cost. If $a$ is currently at depth $e\le d$ and a symbol $x$ of weight $p_x\ge p_a$ occupies the chosen depth-$d$ leaf, swapping them changes the two cost terms from $p_{a}e+p_{x}d$ to $p_{a}d+p_{x}e$, a difference $(p_a-p_x)(d-e)\le 0$. Then place $b$ in the sibling leaf by the same calculation, since its current occupant has weight at least $p_b$. Relabeling leaves preserves the prefix property; the original code was optimal, so the resulting code is still optimal.

Contract the two sibling leaves labeled $a,b$ to one leaf $z$ with weight $p_z=p_a+p_b$. The contracted tree is a prefix code on the reduced alphabet and its cost is the original cost minus $p_a+p_b$, since both leaf depths decrease by one. Conversely, expanding any reduced prefix code by replacing the codeword for $z$ with its two children labeled $a,b$ preserves the prefix property and increases cost by $p_a+p_b$. Therefore contraction sends an optimal original code to an optimal reduced code, and expanding an optimal reduced code gives an optimal original code.

By step 4.1, expansion of that reduced tree is optimal for the original weights. The algorithm terminates and returns a prefix code by step 1.2; the base case step 1.4 and the induction step prove its optimality for every $m\ge 2$.