Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.