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

Abstract

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 $\Omega (n\log n)$ time to be sorted.

Fixed some issues in the early versions

References in corpus (1)

• Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search