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?

$\endgroup$
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.