Whenever there's a discussion about sorting I like to put in a little reminder about the humble Radix Sort which is often overlooked by academics because it's so simple. It deserves more attention as it is super fast: O(kn). Academics disregard it because it won't sort floating point numbers, but the vast majority of real-world use cases deal with alphanumerics, so Radix Sort should get more press than it does.