# Optimal Prefix Free Codes with Partial Sorting +
## 2 Solution
### Algorithm \"Group-Dock-Mix\" (GDM) for the Binary Case
Initialization: Initialize the deferred data structure partial sum with the input; compute the weight currentMinInternal of the first internal node through the operation partialSum\((2)\) (the sum of the two smallest weights); create this internal node, of weight currentMinInternal and children 1 and 2 (the positions of the first and second weights, in any order); compute the weight currentMinExternal of the first unpaired weight (i.e., the first available external node) by the operation select\((3)\); setup the variables nbInternals\(=1\) and nbExternalProcess\(=2\). 2. Grouping: Compute the position \(r\) of the first unpaired weight larger than the smallest unpaired internal node, through the operation rank(currentMinInternal); pair the (\((r-\)nbExternalProcessed) modulo 2) indices to form \(\lfloor\frac{r-\text{nbExternalProcessed}}{2}\rfloor\) pure internal nodes; compute the parity of the number \(r-\text{nbExternalProcessed}\) of unpaired weights smaller than the first unpaired internal node; if it is odd, select the \(r\)-th weight through the operation \(\mathrm{select}(r)\), compute the weight of the first unpaired internal node, compare it with the next unpaired weight, to form one mixed node by combining the minimal of the two with the extraneous weight. 3. Docking: Pair all internal nodes by batches (by Property 1, their weights are all within a factor of two, so all internal nodes of a generation are processed before any internal node of the next generation); after each batch, compare the weight of the largest such internal node (compute it through partialSum on its range if it is a pure node, otherwise it is already computed) with the first unpaired weight: if smaller, pair another batch, and if larger, the phase is finished. 4. Mixing: Rank the smallest unpaired weight among the weights of the available internal nodes, by a doubling search starting from the beginning of the list of internal nodes. For each comparison, if the internal node's weight is not already known, compute it through a partialSum operation on the corresponding range (if it is a mixed node, it is already known). If the number \(r\) of internal nodes of weight smaller than the unpaired weight is odd, pair all but one, compute the weight of the last one and pair it with the unpaired weight. If \(r\) is even, pair all of the \(r\) internal nodes of weight smaller than the unpaired weight, compare the weight of the next unpaired internal node with the weight of the next unpaired external node, and pair the minimum of the two with the first unpaired weight. If there are some unpaired weights left, go back to the Grouping phase, otherwise continue to the Conclusion phase. 5. Conclusion: There are only internal nodes left, and their weights are all within a factor of two from each other. Pair the nodes two by two in batch as in the docking phase, computing the weight of an internal node only when the number of internal nodes of a batch is odd. The combination of those phases forms the GDM algorithm, which computes an optimal prefix free code given an unsorted sets of positive integers. **Lemma 3**. : _The tree returned by the GDM algorithm describes an optimal binary prefix free code for its input._  
In the next section, we analyze the number \(q\) of rank, select and partialSum queries performed by the GDM algorithm, and deduce from it the complexity of the algorithm in term of algebraic operations.