I am currently doing revision for my course and came across the question in the title, I wasn't able to find the answer online so I come to stack overflow for help.

CodePudding user response：

There are no comparison-based sorts that are faster than O(N log N).

Radix sort is O(N) in the size of the input, i.e., O(num_keys * average_length), which can be considered o(n log n) in some contexts.

Counting sort is O(N num_possible_values), which is also o(n log n) in applicable cases.