Why Not: A Sorting Algorithm Based on the Fake-Theory of Intelligent Design
What computer science textbooks don't want you to know.
Image: Sarah Brooks/Flickr
Sorting algorithms are among the most fundamental algorithms in computer science. Sorting is at the very heart of data or even just information in general. Search algorithms usually grow from sorting algorithms, for one thing, and that's about the most fundamental data operation there is. Sorting, which might just be viewed as arranging a bunch of different things in some order, is, well, the substance of order itself. Right?
So, computer scientists are always looking for ways to upgrade sorting algorithms. They've been at it since at least 1956 and new sorting algorithms are released on a regular basis. Around 2013, esoteric programming language enthusiast and comics writer named David Morgan-Mar unveiled his Intelligent Design Sort, an algorithm that doesn't actually sort information and instead just says that it must already be sorted according to the will of a great unknowable being.
Here is Morgan-Mar's description:
The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally Sorted in some way that transcends our naïve mortal understanding of "ascending order". Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.
Morgan-Mar offers a short complexity analysis of the algorithm and finds that, marvelously, it has no complexity at all! It's so simple and efficient that it doesn't even require a computer. "Praise the Sorter!," he writes.
But wait ... what are the implications of such an algorithm? Morgan-Mar includes the following proof submitted by Krishna Kumar, who is presumably another fan of esoteric programming languages/algorithms.
A corollary: All elements are created equal under the Sorter.
Proof: Take a random permutation of the input list; this second list is also Sorted by the same argument as above. This means that any two elements in the two lists with the same index are equal to each other. But the second list was a random permutation; which indicates that every element in the original list is equal to every other element. QED.