Bogosort

In computer science, We (Royal we, as in “We are not amused”) attempt to measure various algorithms quantitatively through various measures like “big theta”, “big omega”, and of course “big O”. “Big O” is basically a measure of the “worst case” of any particular algorithm. For instance, if a search algorithm was something like “look in each hotel room sequentially for my car keys starting at room 1″, then the worst case is that my car keys are in the very last hotel room. If there are n hotel rooms, then my algorithm is O(n) (big O of n).

In sorting algorithms, it is a fact that sorting can’t be done in less than O(n) time. That is, you have to touch each element you want to sort at least once. I was looking through a list of algorithms on Wikipedia (that’s what I do for fun) to check out sorting algorithms that I haven’t heard about yet. I came across the very hilarious Bogosort algorithm. If you were to apply bogosort to a deck of cards, it would consist of playing 52-pick up over and over until the cards end up in sorted order. It’s rated at O(n * n!), which is unbelievable horrible, and could probably be considered the worst sorting algorithm possible.

It also occurred to me that Bogosort is the one thing that both sides of the Intelligent Design debate have in common. ID says that bio-genesis comes from Bogosort, but that some divine force has loaded the dice (not provable). The other side advocates say that given infinite time, Bogosort will eventually sort (which is true).

That’s all I wanted to say–no commentary. I just though Bogosort was funny and that it was a good metaphor.