### Why sorting cannot be done faster than O(n log n)?

- by Jaakko Moisio
- Sept. 12, 2020

Popular comparison sorting algorithms need an order of O(n log n) comparisons to sort an array of size n. But can we do better if we try hard enough? Mathematics says that, in general, we cannot, and here’s the proof.