# Optimal sort algorithm in number of swaps

Given a sequence of $n$ numbers, can it be sorted with $O(n \ln n)$ comparisons and $O(n)$ swaps/moves? Any pointer to publications on that matter or counterarguments showing a $\Omega(n \ln n)$ lower bound would help.

• Any comparison based sorting algorithm will need to perform $\Omega(n \log n)$ comparisons and $\Omega(n)$ swaps in the worst case (cf. CLRS). Jul 6, 2011 at 9:37
• Trivially, you can achieve $O(n)$ moves if you first sort a table that contains the indexes of the elements, and only after that sort the table that contains the elements. Jul 6, 2011 at 10:01
• @jukka well that's cheating coz you moved elements when you sorted the table ... Jul 9, 2011 at 12:58

There exists a stable in-place sorting algorithm with $O(n \log n)$ comparisons and $O(n)$ moves.
See: Gianni Franceschini: Sorting Stably, in Place, with $O(n \log n)$ Comparisons and $O(n)$ Moves. Theory Comput. Syst. 40(4): 327-353 (2007)