There is a mAtHeMaTicAl pRoOf 🤡 that a comparison-based sorting algorithm cannot get more efficient than O(n*log n). That's bullshit. Radix sort et al. — granted, they're not comparison-based.

But there is one comparison-based algorithm that can sort an array in O(n). It's called Stalin sort.

It traverses the array and deletes every item that doesn't appear in order. Boom, problem solved — the array is sorted in O(n), at the expense of losing (most of the) elements.

This is the perfect metaphor of Stalin's politics.

This is one of the questions on my sample exam. I love how the answer is just "use radix sort".