The **package-merge algorithm** is an *O(nL)*-time algorithm for finding an optimal length-limited Huffman code for a given distribution on a given alphabet of size *n*, where no code word is longer than *L*. It is a greedy algorithm, and a generalization of Huffman's original algorithm. Package-merge works by reducing the code construction problem to the binary *coin collector's problem*.^{[1]}

Suppose a coin collector has a number of coins of various denominations, each of which has a numismatic value unrelated to its denomination. The coin collector has run out of money and needs to use some of his coin collection to buy something of cost *N*. He wishes to select a subset of coins from his collection of minimum numismatic value whose denominations total *N*.

The binary version of this problem is that all denominations are powers of 2, that is, 1, 1/2, 1/4, etc. dollars.

Assume that the largest denomination is 1 dollar, and that N is an integer. (The algorithm works even if these assumptions do not hold, by trivial modifications.) The coin collector first separates his coins into lists, one for each denomination, sorted by numismatic value. He then **packages** the smallest denomination coins in pairs, starting from the pair of smallest total numismatic value. If there is one coin left over, it will be the coin of highest numismatic value of that denomination, and it is set aside and ignored henceforth. These packages are then **merged** into the list of coins of the next smallest denomination, again in order of numismatic value. The items in that list are then **packaged** in pairs, and merged into the next smallest list, and so forth.

Finally, there is a list of items, each of which is a 1 dollar coin or a package consisting of two or more smaller coins whose denominations total 1 dollar. They are also sorted in order of numismatic value. The coin collector then selects the least value N of them.

Note that the time of the algorithm is linear in the number of coins.

Let *L* be the maximum length any code word is permitted to have.
Let *p*_{1}, …, *p _{n}* be the frequencies of the
symbols of the alphabet to be encoded. We first sort the symbols so that

With this reduction, the algorithm is *O(nL)*-time and *O(nL)*-space. However, the original paper, "*A fast algorithm for optimal length-limited Huffman codes*", shows how this can be improved to *O(nL)*-time and *O(n)*-space. The idea is to run the algorithm a first time, only keeping enough data to be able to determine two equivalent subproblems that sum to half the size of the original problem. This is done recursively, resulting in an algorithm that takes about twice as long but requires only linear space.^{[1]}

Many other improvements have been made to the package-merge algorithm to reduce the multiplicative constant and to make it faster in special cases, such as those problems having repeated *p _{i}*s.

Methods involving graph theory have been shown to have better asymptotic space complexity than the package-merge algorithm, but these have not seen as much practical application.