Sorting a Low-Entropy Sequence
<|reference_start|>Sorting a Low-Entropy Sequence: We give the first sorting algorithm with bounds in terms of higher-order entropies: let $S$ be a sequence of length $m$ containing $n$ distinct elements and let (H_\ell (S)) be the $\ell$th-order empirical entropy of $S$, with (n^{\ell + 1} \log n \in O (m)); our algorithm sorts $S$ using ((H_\ell (S) + O (1)) m) comparisons.<|reference_end|>
@article{gagie2005sorting,
    title={Sorting a Low-Entropy Sequence},
    author={Travis Gagie},
    journal={arXiv preprint arXiv:cs/0506027},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0506027},
    primaryClass={cs.DS}
}