# Optimal Prefix Free Codes with Partial Sorting +
## 2 Solution
### Algorithm \"Group-Dock-Mix\" (GDM) for the Binary Case  
There are five main phases in the GDM algorithm: the initialization, three phases (grouping, docking, and mixing, giving the name \"GDM\" to the algorithm) inside a loop running until only internal nodes are left to process, and the conclusion:  
1. In the initialization phase, initialize the partial sum deferred data structure with the input, and the first internal node by pairing the two smallest weights of the input. 2. In the grouping phase, detect and group the weights smaller than the smallest internal node: this corresponds to a run of consecutive \(E\) in the EI signature of the instance. 3. In the docking phase, pair the consecutive positions of those weights (as opposed to the weights themselves, which can be reordered by future operations) into internal nodes, and pair those internal nodes until the weight of at least one such internal node becomes equal or larger than the smallest remaining weight: this corresponds to a run of consecutive \(I\) in the EI signature of the instance. 4. In the mixing phase, rank the smallest unpaired weight among the weights of the available internal nodes, and pairs the internal node of smaller weight two by two, leaving the largest one unpaired: this corresponds to an occurrence of \(IE\) in the EI signature of the instance. This is the most complicated (and most costly) phase of the algorithm. 5. In the conclusion phase, with \(i\) internal nodes left to process (and no external node left), assign codelength \(l=\lfloor\log_{2}i\rfloor\) to the \(i-2^{l}\) largest ones and codelength \(l+1\) to the \(2^{l}\) smallest ones: this corresponds to the last run of consecutive \(I\) in the EI signature of the instance. The algorithm and its complexity analysis distinguish two types of internal nodes: pure nodes, which descendants were all paired during the same grouping phase; and mixed nodes, each of which either is the ancestor of such a mixed node, or pairs a pure internal node with an external node, or pairs two pure internal nodes produced at distinct phases of the GDM algorithm. The distinction is important as the algorithm computes the weight of any mixed node at its creation (potentially generating several data structure operations), whereas it defers the computation of the weight of some pure nodes to later, and does not compute the weight of some pure nodes. We will discuss this further in Section 5 about the non instance optimality of the solution presented. Before describing each phase more in detail, it is important to observe the following invariant of the algorithm:  
**Property 1**. : _Given an instance of the optimal binary prefix free code problem formed by \(n>1\) positive weights \(W[1..n]\), between each phase of the algorithm, all unpaired internal nodes have weight within a constant factor of two (i.e., the maximal weight of an unpaired internal node is strictly smaller than twice the minimal weight of an unpaired internal node)._  
Proof. : The generally property is proven by checking that each phase preserves it:  
1. Initialization: there is only one internal node at the end of this phase, hence the conditions for the property to stand are created. 2. Grouping: no internal node is created, hence the property is preserved. 3. Docking: pairing until at least one internal node has weight equal or larger than the smallest weight of a remaining weight (future external node) insures the property. 4. Mixing: as this phase pairs all internal nodes except possibly the one of largest weight, the property is preserved. 5. Conclusion: A single node is left at the end of the phase, hence the property. As the initialization phase creates the property and each other phase preserves it, the property is verified through the execution of the algorithm. We now proceed to describe each phase in more details:  
1.