In the algebraic decision tree, the result is clear: Elmasry and Belal (Verification Of Minimum Redundancy Prefix Codes)'s lower bound shows that the worst case complexity of computing an optimal prefix free code over all possible sequences of $\sigma$ frequencies is $\Theta(\sigma\lg\sigma)$.In the $\Omega(\lg \sigma)$-word RAM model, combining Van Leeuwen's reduction to sorting (On The Construction Of Huffman Trees) with any $O(\sigma\lg\lg\sigma)$ sorting algorithm in the RAM model yields an upper bound of $O(\sigma(1+\lg\lg\sigma))$, which many people seem to assume to be optimal, probably by analogy with the situation in the algebraic decision tree model. But the only lower bound available is $\Omega(\sigma)$, the cost of reading the frequencies, leaving a gap between the two bounds.What is the best upper bound known on the asymptotic complexity of computing an optimal prefix free code in the word RAM model? Is it $\Theta(\sigma\lg\lg\sigma)$ or $\Theta(\sigma)$? Or somewhere in between?
What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?
ds.algorithms;sorting;prefix free code