Linear time sorting of skewed distributions
Edleno Silva de Moura, Gonzalo Navarro, Nívio Ziviani · 2003
The article presents an efficient linear average time algorithm to sort lists of integers that follow skewed distributions. It also studies a particular case where the list follows Zipf's distribution, and presents an example application where the algorithm is used to reduce the time to build word-based Huffman codes.