1
$\begingroup$

I've read an article (German) about different sorting algorithms where the author states this:

[Smoothsort] is a sorting algorithm that uses swaps to sort and does not need any extra external allocated memory. Because of this it can't be stable, because if it was, it needed $O(n^2)$ comparisons in the worst case. (This statement is a hypothesis of mine. I'm very sure it holds, although I have yet to show it)

I wasn't able to find an algorithm on my own that satisfies the criteria (in-place, stable, faster than $O(n^2)$ in the worst case). Is that hypothesis true? If yes, how can one show that it holds?

2 Answers 2

6

No. There is an O(n log n)-time comparison-based stable in-place sorting algorithm [Tra77].

[Tra77] Luis Trabb Pardo. Stable sorting and merging with optimal space and time bounds. SIAM Journal on Computing, 6(2):351–372, June 1977. http://dx.doi.org/10.1137/0206025

2

The wikipedia page on stable sorts pointed to this description of a stable inplace mergesort that is supposed to be easy to understand