I'm curious if anything like this has been proved, or is even possible to prove a statement like: "Out of all sorting algorithms, this one has the lowest time complexity for the worst-case."

Or stated more specifically, the statement could look like: "Quicksort has the lowest time complexity for worst case of all sorting algorithms because X, Y, Z"

  • 1
    $\begingroup$ Any basic Google search such as "complexity of sorting" would have answered this question for you. $\endgroup$ – David Richerby Feb 27 '18 at 15:25
  • $\begingroup$ I did a cursory look at the complexity of sorting but all I found were just tables of time complexities. Also "Sortation" is actually a word. Not sure if you down voted me for that, but you shouldn't have. merriam-webster.com/dictionary/sortation $\endgroup$ – Nathvi Feb 27 '18 at 15:49
  • $\begingroup$ I downvoted for lack of research; it would be completely unfair to downvote for something I'd fixed. "Sortation" may well be a word but it's never used in this context. (For example, the Google n-gram database has literally zero entries for "sortation algorithm"). $\endgroup$ – David Richerby Feb 27 '18 at 15:56
  • $\begingroup$ Any basic Google search of the word "sortation" would have shown you that it was a real word. $\endgroup$ – Nathvi Feb 27 '18 at 15:58
  • $\begingroup$ You gave a dictionary link. I can see that it's a real word. But that doesn't matter: it's not the word that's used to describe this kind of algorithm. "Ordering" is also a real word but if you'd said "ordering algorithm", I'd have edited that, too. $\endgroup$ – David Richerby Feb 27 '18 at 16:02

Sorting with comparisons is know to be an $\Omega(n\log n)$ problem and we know several sorting algorithms that reach that bound in the worst case (Heapsort, Mergesort).

(The justification is short: the decision tree able to distinguish among the $n!$ possible permutations of the input has a height at least $\log_2 n!$.)

In some special cases comparison-less methods are possible and may lead to an $\Omega(n)$ bound. Worst-case optimal algorithms are also available (Histogramsort).


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.