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 Jul 6 '11 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$ – Jukka Suomela Jul 6 '11 at 10:01
  • $\begingroup$ @jukka well that's cheating coz you moved elements when you sorted the table ... $\endgroup$ – Jesse Zixi Zhang Jul 9 '11 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)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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