Outputs: When There is Madness to the Method

Considering that algorithms are human artifacts, it is very interesting that there even is such a thing as a bad algorithm. (It's also very interesting that apparently it is possible to make a joke in the form of an algorithm.) The phenomenon would seem to tell us something about the "essence" of an algorithm since even a severely deformed sorting algorithm is still recognized as a sorting algorithm. Consider a classic example:


START: given an array A[1..n]

STEP 1: IF (A is in sorted order) THEN [HALT] ELSE [GOTO STEP 2]

STEP 2: DO [randomly shuffle A[1..n]]

END


, which is more commonly known as "bogo-sort" and can be traced back at least to 1984[1]. There are some amusing quantitative analyses of such algorithms[2], but what stands out to me is that this can be called a sorting algorithm at all. I'm not disputing that bogo-sort is indeed a well-defined procedure, or that it eventually sorts its input array. What seems noteworthy is that we have here something that really is a sorting algorithm, but only just barely.

The only sense in which bogo-sort is a sorting algorithm is that, if and when it stops, the input array will be sorted. If we were to change the condition in STEP 1 to anything other than "Is A sorted?", we might say we have some kind of algorithm, but it would certainly not be a sorting algorithm. Put another way, we could change the condition to (almost) anything else and get an algorithm that is not a sorting algorithm. Bogo-sort is nothing other than a slightly constrained version of a very generic and very disorderly procedure (i.e. moving things around at random); its "sorting" is really nothing other than a discrimination applied to an otherwise indiscriminate process.

Perhaps another appropriate (but less snappy) name for this procedure would be "tautological sort". The array is sorted when the program says they're sorted, or rather, when the programmer says the program should stop. By way of analogy, this would be something like "straightening up" a messy room by going in and hurling objects about at random, and stopping whenever it was that you declared the room to be clean. ("Mission accomplished!") In this case, the output makes the program, and the notions of the programmer make the output. Maybe this is not especially surprising in and of itself, but it makes for a stretch of thin and blurry line separating the orderly and the chaotic, or the desirable and the undesirable.

The authors who have already commented on this curiosity raise a class of interesting questions: for any given objective, what is the worst possible means of attainment? ("The Pyrrhic Problem") This is worth asking if for no other reason than to point out that there are exceptionally bad ways of attaining almost any object. Although it seems little more than an academic curiosity when applied to algorithms, the question becomes strangely illuminating when applied to any number of real-world enterprises. Consider, for instance, how useful toilet paper is, but consider also that huge swaths of forest are cut down to produce it. It seems not only that are ends sometimes used to justify means, but that utter chaos circumscribed by an end can become a means.

---

[1] Broder, Andrei, Stolfi, Jorge. "Pessimal Algorithms and Simplexity Analysis", ACM SIGACT News, 16:49-53, 1984.

[2] Gruber, Hermann, Markus Holzer, Oliver Ruepp. "Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms", FUN 2007, LNCS 4475, p183-197, 2007.