# An in-place sorting algorithm performing $O(n\log n)$ comparisons and $O(n)$ data moves

In this paper we give a positive answer to the long-standing
problem of finding an in-place sorting algorithm performing $O(n\log n)$
comparisons and $O(n)$ data moves in the worst case.
So far, the better in-place sorting algorithm with $O(n)$ moves was
proposed by Munro and V. Raman. Their algorithm requires $O(n^{1+\epsilon})$
comparisons in the worst case, for any $\epsilon > 0$. Later, Katajainen and
Pasanen discovered the first in-place algorithm with $O(n\log n)$ comparisons and $o(n\log n)$ moves, namely $O(n\log n/\log\log n)$ moves. Our algorithm achieves the same number of comparisons but with $O(n)$ moves, which is asymtotically optimal.