Linear Time Sorting of Skewed Distributions

Edleno de Moura, Gonzalo Navarro and Nivio Ziviani

This work 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 the Zipf's distribution, and presents a example application where the algorithm is used to reduce the time to build word-based Huffman codes.