An In-Place Sorting with O(n log n) Comparisons and O(n) Moves

Gianni Franceschini, Viliam Geffert

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This so…