Is there no sorting algorithm with all specific desired properties?

On the Sorting Algorithms website, the following claim is made:


The ideal sorting algorithm would have the following properties:

• Stable: Equal keys aren't reordered.

• Operates in place, requiring $O(1)$ extra space.

• Worst-case $O(n\cdot\lg(n))$ key comparisons.

• Worst-case $O(n)$ swaps.

• Adaptive: Speeds up to $O(n)$ when data is nearly sorted or when there are few unique keys.

There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

My question is, is it true that


there is no [sorting] algorithm that has all of these properties

and if so, why? What is it about these properties that makes all of them simultaneously impossible to fulfill?

WikiSort and GrailSort are two fairly recent algorithms that do in place, stable, worst case $O(n\ lg(n))$ key comparisons. Unfortunately I don't understand them well enough to know if they approach $O(n)$ swaps or are adaptive so I don't know whether they violate the fourth and fifth conditions you have.

From looking at the paper "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner linked to by the WikiSort GitHub page, Kim and Kutzner claim to have a 'merge' operation that is $O( m (\frac{n}{m} + 1))$ (WikiSort is a variant of Mergesort) but I'm not sure if that translates to WikiSort having $O(n)$ swaps. GrailSort is claimed to be faster (in the WikiSort GitHub page) so I could imagine that it's likely they both have worst case $O(n)$ swaps and are adaptive.

If anyone does manage to understand WikiSort and/or GrailSort I would appreciate them also answering my open question about it

StackExchange Computer Science Q#44539, answer score: 6