The Weird Cousins of Bogosort

I thought Bogosort was the most unnecessary algorithm. I was wrong. Here are some more weird algorithms that are related to the Bogosort:

  1. Bogobogosort

    For Bogosort, we check if the list is sorted and if not then we perform a random shuffle and check again. Bogobogosort builds on that and specifies how to check if the list is sorted, using recursion of course.

    To be completely honest, I went through the algorithm and have no desire to perform an analysis but this blog not only shares my sentiments but also provides a detailed analysis, so please refer to the same for more details.

  2. Gorosort

    Gorosort operates such that, while the list is not in order, it will randomly permute a subset of all the elements. This algorithm was actually designed for the following Google Code Jam problem:

    "Goro has 4 arms. Goro is very strong. You don't mess with Goro. Goro needs to sort an array of N different integers. Algorithms are not Goro's strength; strength is Goro's strength. Goro's plan is to use the fingers on two of his hands to hold down several elements of the array and hit the table with his third and fourth fists as hard as possible. This will make the unsecured elements of the array fly up into the air, get shuffled randomly, and fall back down into the empty array locations."

  3. Bozosort

    Another variation of random sort, Bozosort chooses two numbers in an array randomly, swaps them and checks if the resulting array is sorted. The average complexity is expected to be O(n!) but it is hard to calculate.

  4. Worstsort

    No, this is not that one sauce that no one can pronounce. Worstsort is a variation of badsort which will provably terminate in finite time but the term "finite" is used very loosely. Worstsort is parameterized by a function on natural numbers, and calls badsort with a recursion depth given by the function f applied to the length of the list. To understand how bad it is, lets take function f to be Ackermann's function. While a list of length 1 or 2 will be easily sorted, length 3 and beyond become completely hopeless. Therefore, to sort a list arbitrarily badly, one would execute worstsort(L, f) = badsort(L, f(length(L))), where length(L) is the number of elements in L. The resulting algorithm has complexity O((n!(f(n)))2) where n!(m) is the factorial of n iterated m times. Yikes.

  5. Slowsort

    One of the fundamental concepts of Computer Science is Divide and Conquer. Let me introduce you to Multiply and Surrender. Slowsort is from a hilarious paper titled "Pessimal Algorithm and Simplixity Analysis" which can be found here. As for the implementation, let's assume we are sorting an array using Slowsort. We sort the first half , recursively and repeat the same for the second half. Next we find the maximum of the whole array by comparing the results obtained in the first two steps, and place the maximum at the end. Now we have to sort the entire array, minus the last element, recursively.

  6. Quantum Bogosort

    When I first came across the Quantum Bogosort, I had to double check and see if it was a formally recorded algorithm. This is how it works:

    1. Generate a random permutation of input using a quantum source of entropy.
    2. Check if list is sorted. If not sorted, destroy the universe.

    Simple, right? The complexity is just as easy to analyse. All you have to do is to assume that the many-worlds interpretation holds, and if so, the use of this algorithm would leave atleast one universe where the input is sorted in O(n) time.

    This is obviously a computer science inside joke. We have those.

  7. Miracle Sort

    This algorithm is straight from the Bible. It checks the array repeatedly until a miracle occurs and it is sorted. Through the divine intervention. No, I did not make this up. The order of the array is never shuffled and the hypothetical time complexity is O(∞) but the best case complexity is O(n) when the array is sorted.