Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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.

share|cite|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|cite|improve this answer

Your Answer


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.