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.