# Bounds on computational complexity of a sorting algorithm

Assume that you are designing a sorting algorithm that uses an operation $x \leq y$ that have 3 possible results:

• $x < y$

• $x = y$

• $x > y$

Can your algorithm do better than ${\cal \Omega}(n \log n)$?

• This question is incompletely posed because it doesn't state whether the complexity bounds are for the best case, the worst case or the average case. Any trivial sorting algorithm--such as insertion sort, or bubble sort--will have best-case complexity lower than ${\cal \Omega}(n \log n)$. – David G. Stork Sep 27 '17 at 17:28

I will for simplicity assume that we are just talking about the worst case scenarios. In practical terms though that isn't really something you should take for granted as being the sole indicator of a good algorithm. There's also the best case or the average case scenario (together these $3$ are the algorithms time complexity), and space complexity (how much memory is taken up by the algorithm) etc.
For comparison sorts (Merge Sort, Quicksort, Shell Sort, Insertion Sort, Heapsort etc.) the best known is as far as I know $\mathcal{O}(n\log{}n)$.
For most practical purposes though we use Quicksort because it has an average time complexity of $\mathcal{O}(n\log{}n)$ (even though it's worst case is $\mathcal{O}(n^2)$), and a space complexity of $\mathcal{O}(\log{}n)$.