This is by no means new, but it's not terribly well known and I think it's both beautiful and hilarious. Almost all quicksort implementations take quadratic ti

This is by no means new, but it's not terribly well known and I think it's both beautiful and hilarious. Almost all quicksort implementations take quadratic time in the worst case. They generally do a rather good job of avoiding that worst case, by careful choice of pivots[1]. McIlroy has a very simple technique for making that choice produce bad results in almost all quicksort implementations. Unfortunately, he has to cheat a bit. His code doesn't construct an array full of evil values. Rather, he has an adaptive comparison function that, in effect, constructs the array of evil during the sorting process. (But it always behaves consistently; the elements of the array are, so to speak, undecided until the sorting routine looks at them, but they don't change after they've been looked at.) [1] For those who don't know, here's the quicksort algorithm: Choose one element of your array (the "pivot"); partition the array into things smaller than the pivot and things larger than the pivot; then, recursively, sort the two parts you just made. This works well, at least when you aren't facing McIlroy's evil adversary, because (1) you can do the partitioning operation very efficiently and (2) if you're not very unlucky with your choice of pivot you usually succeed in dividing the array into two parts of roughly equal size. But if the pivot is, say, always the smallest element of your array, you'll get terrible results.