No, O(n log n) is a proven lower bound for comparison-based sorting. The argument: a comparison sort distinguishes among the n! possible orderings using yes/no comparisons, and a binary decision tree distinguishing n! outcomes must have height at least log₂(n!), which is Θ(n log n) by Stirling's approximation, so some input forces that many comparisons. You can beat O(n log n) only by not comparing elements: non-comparison sorts like counting sort, radix sort, and bucket sort run in O(n) or O(n+k) by exploiting structure in the keys (small integer range, fixed-width digits). Those are great when applicable, e.g. radix-sorting fixed-width integer sensor IDs, but they require known, bounded key structure and often extra memory (counting sort needs an array sized to the key range). So: O(n log n) is optimal for general comparison sorts; sub-linearithmic sorting requires giving up the comparison model and exploiting the keys.
Data Structures & Algorithms · Interview question
Is there a comparison sort faster than O(n log n)?
A strong answer
What a weak answer sounds like
You know the answer. Do you know what gets you dinged?
Pro breaks down the answer most candidates actually give to this question — and the specific reason an interviewer marks it down. It’s the difference between sounding correct and sounding senior, on all 472 questions.
From the lesson
Sorting Basics
The O(n²) simple sorts vs the O(n log n) fast ones, and why on embedded the simple, in-place insertion sort often beats the asymptotically-better choice at small n.