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.

  • $\begingroup$ Any comparison based sorting algorithm will need to perform $\Omega(n \log n)$ comparisons and $\Omega(n)$ swaps in the worst case (cf. CLRS). $\endgroup$
    – Kaveh
    Commented Jul 6, 2011 at 9:37
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Jul 6, 2011 at 10:01
  • $\begingroup$ @jukka well that's cheating coz you moved elements when you sorted the table ... $\endgroup$ Commented Jul 9, 2011 at 12:58

1 Answer 1


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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.