2
$\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$

2 Answers 2

Reset to default
9
$\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$
3
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .