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$
$\endgroup$
3
-
$\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$– KavehJul 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$– Jukka SuomelaJul 6, 2011 at 10:01
-
$\begingroup$ @jukka well that's cheating coz you moved elements when you sorted the table ... $\endgroup$– Jesse Zixi ZhangJul 9, 2011 at 12:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)
http://www.springerlink.com/content/d7348168624070v7/
