An in-place sorting algorithm performing $O(n\log n)$ comparisons and $O(n)$ data moves
Gianni Franceschini · UnipiEprints Open Archive (Università di Pisa) · 2003
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.