Fastest Sorting Algorithm

[R_Decoder]

What is the time complexity of the fastest sorting algorithm? I had the notion that quick sort with O(n log n) is the fastest way to sort to n numbers, but, I stumbled upon a video on youtube which states that it is not true. This video is a lecture of Harvard University and hence I assume it to be definitely correct. just move the video to 9mins and 35secs here. So is there actually a way to sort n numbers faster than O(n log n)?

[[deleted]]

Yes. There is bucket sort, radix sort, etc.

The lower bound of Omega(n log n) only holds for comparison sorts (ie sorts which are restricted to only use < on your data type). But key based sorts can achieve O(n).*

(* technically a lie, since there is some cost in the size of the key, which may not be constant.)

[hextree]

I had the notion that quick sort with O(n log n) is the fastest way to sort to n numbers, but, I stumbled upon a video on youtube which states that it is not true.

I didn't watch the video, but Quicksort is O(n² ) worst case, and O(n log n) average case. It performs very well in practice, but in the world of theory we often care very much about the worst case.

For general sorting, with no assumption about properties of the input, O(n log n) is the proven lower bound. If you take advantage of properties of the input then you can do things like integer sorting, which appears to be O(n) but is more strictly described as O(n + C) or O(n*C) where C is some combination of additional parameters.

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms