# Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time $$O(n \sqrt{\log n}),$$ and linear space. The paper seems reasonable, though I am not an expert in sorting algorithms.

If correct, this would be a significant, I believe, at least theoretically.

The presentation of the main argument is somewhat informal and nontraditional, however.

Has anyone noticed/commented on this paper? It seems that the same author, Yijie Han, has published a related result on integer sorting, as discussed in Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

• "We assume that a variable $v$ holding a real value has arbitrary precision and $int(v \cdot 2^a)$ for a nonnegative integer $a$ can be computed in constant time." This smells fishy, see computational-geometry.org/mailing-lists/compgeom-announce/… – Sasho Nikolov Jan 6 '18 at 3:12
• Every computable function from reals to integers is constant. – Andrej Bauer Jan 25 '18 at 7:12
• Andrej, that is in a different model of computation. – Kristoffer Arnsfelt Hansen Jan 25 '18 at 8:11
• Aaand now I no longer believe his earlier paper. – Jeffε Jan 30 '18 at 1:52

• what is the connection to $PSPACE\in P$ or $\#P\in FP$? – T.... Jan 25 '18 at 11:06