Sort Algorithms

Okay, this one makes me happy. New algorithms - new applications of theory - that I can actually use seem few and far between, but I just ran into one.

David Musser's Introsort is an algorithm from the late 90's that starts with quicksort, and switches to heapsort if quicksort isn't expected to perform well on the actual dataset. It has the speed of quicksort, but in a worst-case-scenario, it only falls back to O(n log n), which is awesome. (Quicksort's worst case is n^2)

So, why would that matter?

Well, if you're maintaining an important server that contains lists of data, and the server sorts incoming data to store it, an attacker could send you a list designed to really, really ruin your day. A DNS server might be a decent example of this. Or even a payment gateway that sorts by customer ID before it gets going.