Sorting Real Numbers in $O(n\sqrt{\log n})$ Time and Linear Space
Yijie Han · arXiv (Cornell University) · 2017
We present an $O(n\sqrt{\log n})$ time and linear space algorithm for sorting real numbers. This breaks the long time illusion that real numbers have to be sorted by comparison sorting and take $Ω(n\log n)$ time to be sorted.