22
$\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?

$\endgroup$
  • 4
    $\begingroup$ They probably just mean that no known sorting algorithm has all these properties. $\endgroup$ – Yuval Filmus Jul 19 '15 at 16:40
  • 3
    $\begingroup$ Is there even one comparison-based sort meeting 3&4? $\endgroup$ – greybeard Jul 19 '15 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 '15 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 '15 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 '15 at 21:51
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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\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.

$\endgroup$
  • 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 '15 at 9:23
  • $\begingroup$ Yes, but is it provably possible or impossible? $\endgroup$ – James Faulcon Mar 7 '16 at 18:19
1
$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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