# Proving an algorithm must have the lowest time complexity for sorting in the worst case

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"

• Any basic Google search such as "complexity of sorting" would have answered this question for you. – David Richerby Feb 27 '18 at 15:25
• 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 – Nathvi Feb 27 '18 at 15:49
• 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"). – David Richerby Feb 27 '18 at 15:56
• Any basic Google search of the word "sortation" would have shown you that it was a real word. – Nathvi Feb 27 '18 at 15:58
• 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. – 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).