I say O(n log n) is the best we have got, because all the algorithms that lets us sort with O(n) they just do it at the best case.
Each algorithm has a best, average and worst case when you are going to calculate the O.
As what we can see in websites, O(n) mostly (always really) happens when we give the algorithm the best array case to start with.
but there are some algorithms that have a good O on both sides (best/worst case) and they are both O(n log n) which is good and fair enough. we can also look at the average to see if the algorithm worth it or not.
O(n^2) is soooo big to even consider it! imagine you have a word (or array) of 20 characters! then computer is going to do 20*20 operations!
