23
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ They probably just mean that no known sorting algorithm has all these properties. $\endgroup$
    – Yuval Filmus
    Jul 19, 2015 at 16:40
  • 3
    $\begingroup$ Is there even one comparison-based sort meeting 3&4? $\endgroup$
    – greybeard
    Jul 19, 2015 at 18:10
  • 4
    $\begingroup$ @JohnFeminella It needs at least $\Omega(n \cdot \log(n))$ comparisons, but how does that tell us anything about the number of swaps? $\endgroup$
    – Tom van der Zanden
    Jul 19, 2015 at 19:21
  • 2
    $\begingroup$ @JohnFeminella Nitpick: "better than $O(\_)$" is an empty statement. You should use $\Omega$ or $\Theta$ if you want to talk about lower bounds. $\endgroup$
    – Raphael ♦
    Jul 20, 2015 at 6:02
  • 1
    $\begingroup$ Any sorting algorithm can be made stable by adding as secondary key the original element position. However, that makes it not in place as it would take O(n) extra memory. $\endgroup$
    – Giovanni Botta
    Jul 20, 2015 at 21:51

4 Answers 4

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

Dijkstra's smoothsort comes close, but isn't stable.

Improve this answer
$\endgroup$
2
$\begingroup$

No known algorithms satisfy all of these properties. These properties became sought after as we developed more sorting algorithms. For example, bubble sort (arguably the most primitive sorting algorithm), was most likely non-stable the in the first implementation, but was designed to be stable as computer scientists sought to make it more efficient in later implementations. So, computer scientists most likely picked the best traits from the best algorithms, and as a result, you have brought up a list of all of these desirable traits. In reality, it is difficult to have the best of all worlds in anything. Not impossible, but possibly impossible with our current architectures.

P.S. Use Big-O ($O$) as an asymptotic upper-bound, and Big-Omega ($\Omega$) as an asymptotic lower-bound. Theta ($\Theta$) for the in between.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Welcome! This is nice but I don't see what stability has to do with efficiency: it's merely a preference that sections of the list with identical keys shouldn't be "randomly" permuted by the algorithm. $\endgroup$
    – David Richerby
    Aug 13, 2015 at 9:23
  • $\begingroup$ Yes, but is it provably possible or impossible? $\endgroup$
    – James Faulcon
    Mar 7, 2016 at 18:19
2
$\begingroup$

(Even though this is an old question, I stumbled upon it and so might others.)

There indeed is an algorithm that satisfies (1) - (4) and the second half of (5), so comes very close to the above requirement. It is described in [1] and combines several tricks invented over the last decades.

[1]: Franceschini, G. Theory Comput Syst (2007) 40: 327. https://doi.org/10.1007/s00224-006-1311-1

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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