<p>There exists a stable in-place sorting algorithm with $O(n \log n)$ comparisons and $O(n)$ moves.</p>

<p>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)<br>
<a href="http://www.springerlink.com/content/d7348168624070v7/" rel="nofollow">http://www.springerlink.com/content/d7348168624070v7/</a></p>

CC BY-SA 3.0
2011-07-06T10:10:15.747Z
2011-07-06T10:10:15.747Z
Snowie
<p>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.</p>

CC BY-SA 3.0
2011-07-06T09:37:05.360Z
Any comparison based sorting algorithm will need to perform $\Omega(n \log n)$ comparisons and $\Omega(n)$ swaps in the worst case (cf. CLRS).
Kaveh
CC BY-SA 3.0
2011-07-06T10:01:50.940Z
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.
Jukka Suomela
CC BY-SA 3.0
2011-07-09T12:58:13.630Z
@jukka well that's cheating coz you moved elements when you sorted the table ...
Jesse Zixi Zhang
<cc.complexity-theory><ds.algorithms>
Optimal sort algorithm in number of swaps
Jesse Zixi Zhang
# Optimal sort algorithm in number of swaps

(Asked by: username_0 on 2011-07-06)

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.

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: Any comparison based sorting algorithm will need to perform $\Omega(n \log n)$ comparisons and $\Omega(n)$ swaps in the worst case (cf. CLRS).  
> **username_2**: 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.  
> **username_0**: @jukka well that's cheating coz you moved elements when you sorted the table ...  

---

## 1 answers

### Answer by username_3 on 2011-07-06. Score: 15 | Accepted answer

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/>


---

