Sorting Real Numbers in $O(n\sqrt{\log n})$ Time and Linear Space

Yijie Han

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 sor…