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.

2 comments:

峻龍 said...

唯有穿鞋的人,才知道鞋的哪一處擠腳......................................................................

mick129 said...

I love a good sort algorithm. Several years ago I needed to sort some floating point numbers and Radix sort pleased me so much.