De-optimizing Sorting Algorithms to O(∞)
Experiments done in computer science are not that expensive. You may have done dissections in biology class, where each frog dissection kit can cost around $20, or upwards of $30 in the case of fetal pigs. It can get even more expensive with a titration lab kit for chemistry, costing well over $50 per unit. In computer science, there may be a cost for hardware, but it’s not like computer hardware is one-time use. Computer science experiments can be conducted using the same computer that you use for spreadsheets, browsing YouTube, and playing games. Simply running a few lines of code constitutes a computer science experiment, with no significant dollar cost to it. As a result, the most “expensive” cost of a computer science experiment is not money, but instead, time.
Time complexity is the computational complexity that describes the amount of time it takes a computer to run an algorithm. Lower time complexities are better, so long as the task is still being completed properly. In computer science it’s also important to consider space complexity (how much memory the computer uses), but I’ll be focusing on time complexity for this blog post.
Since finding the exact running time of a program or algorithm can be quite difficult, getting an approximation through analyzing asymptotic behavior (or how running time increases as input size gets infinitely large) is often the accepted standard.
This takes the form of Big O notation, which forms the upper bounds of running time for an algorithm in terms of n, or input size.
The goal of optimizing an algorithm is to make it as close as possible to O(1), which is constant time. A constant time algorithm doesn’t even vary in running time when n is changed, and thus, is the fastest algorithm possible. Of course, not every problem can be solved with an O(1) algorithm, since the parameters of the task in question place limitations on how efficient an algorithm can be. To measure algorithm efficiency, we can take a look at sorting algorithms, which sort data into a specific order (typically smallest to largest). For example, it’s widely regarded that quicksort, which has a running time of O(nlogn), is one of the fastest sorting algorithms. When given a set of unordered data, it’s actually impossible to bring the time complexity down to O(n). After all, it takes O(n) time to simply traverse through an entire array, which isn’t nearly the same task as sorting it. There are several variations of quicksort, such as mergesort and Timsort, which also have running times of O(nlogn), that differ only in best case scenarios (Timsort wins here). These O(nlogn) algorithms are essentially the best of the best when it comes to sorting algorithms. When it comes to sorting a list in Python as quickly as possible, there’s no need to implement your own method, since Timsort has already been set to the standard sorting algorithm since version 2.3. This doesn’t mean that there is no reason to study up on insertion sort, or selection sort for that matter. Understanding less efficient sorting methods, analyzing their big O time complexities, and implementing them yourself comes with its own fundamental benefits for computer science.
It seems like the world has long since figured out the most efficient sorting algorithms (naturally), but what about the other end of the spectrum? Can we purposely design a sorting algorithm to take years, or even centuries? How inefficient can we get?
I’d like to interject with some forewarning here: Do NOT use the following algorithms in actual practice. There are far more efficient sorting algorithms already in use, and getting “creative” with your silly implementation of monkey sort when it comes to your coding interview or backend development project will not end well.
Bogosort
Bogosort, otherwise known as monkey sort, permutation sort, or random sort, is an incredibly inefficient sorting algorithm whose performance is entirely based on luck. You heard that right — nothing in bogosort’s code actually manipulates data into the correct order intentionally. Instead, bogosort organizes the array into a random permutation and then checks if that permutation is ordered. If it isn’t, then it tries again with another arbitrary permutation.
Sorting algorithms are composed of two steps, which are looped through iteratively or recursively: (1) Setting the array (or part of it) into the correct order through array index manipulation and (2) checking for proper array index manipulation. If the second step doesn’t sound familiar to you, it’s because standard sorting algorithms have it “built-in” to the first step. For instance, a selection sort goes through the unsorted part of the array looking for the smallest value, and then places it at the end of the sorted section. By repeating this process, it effectively performs the proper array index manipulation without needing a check afterwards. This falls in stark contrast with bogosort, which performs random array index manipulations and then distinctly, checks if all those operations (by sheer chance) resulted in the ordered array. To get a better idea of how bogosort works, let’s look at a Java implementation. You can find the code on my GitHub here, but I’ve also embedded it via a gist below:
I’ve added quite a few comments that explain most of the code, but I also want to give a more in-depth explanation. Let’s start with the core of bogosort, on line 21:
swap(a, i, (int)(Math.random()* a.length));This line of code swaps two indices, i, which is defined by the for loop, and a random index (which can be the same value as i). Since the for loop causes i to go through the entire array, this line effectively randomizes the array by swapping every single index with a random index. Using a helper function (in this case, swap) isn’t necessary. You can just write the code for the swap right in the for loop if you wish. As you may have realized, this for loop constitutes the “array index manipulation” part of a sorting algorithm, but as I mentioned before, the check for proper order is distinct in bogosort. Let’s take a look at that next. I’ve substituted the for loop with a “randomize” comment.
boolean flag = false;
while (!flag){
// randomize
flag = inOrder(a);
}After substituting the for loop, the code becomes very simple. The boolean variable called flag is initialized to false and keeps track of the sorted status of the array. This is why the condition of the while loop is !flag, since a while loop will only run if its condition is true, and we want to run the loop so long as the array is NOT sorted (in other words, when flag is false).
After randomizing the array, flag is set to the boolean value of the statement: “The array is in order.” This is accomplished with the helper function, inOrder, which like swap, isn’t necessary. Thus, if the array is not sorted, the loop will run again, randomizing the array to a permutation (most likely a different one, depending on the size of the array) and setting flag to the ordered status again. If a randomized permutation happens to be in proper order, then flag is set to true, the while loop terminates, and bogosort is complete.
For those of you familiar with bogosort, you may have noticed that my implementation of bogosort isn’t as efficient as possible (obviously). What I’m referring to is at the very beginning of the bogosort method itself; it’s missing one crucial check:
public static void bogoSort(int[]a){
// What's missing here?
boolean flag = false;If you look through forums discussing inefficient sorting algorithms, bogosort is bound to pop up. It’s essentially the gold standard for slow sorting algorithms (although there are slower ones, we’ll get to those), and even so, it can be the fastest sorting algorithm, which is heavily dependent on the implementation and test case. Caught on yet?
Two combinations of implementations and test cases can allow bogosort to finish in O(n) time, assuming that big O has been restricted to a best case domain:
- An array is given as input, is randomized by bogosort’s first iteration into the correct order, and is confirmed to be in order by the algorithm.
- An ordered array is given as input, and bogosort immediately checks and confirms that it is in order.
The key difference between these two is that the second implementation requires a check by inOrder at the start of bogosort:
public static void bogoSort(int[]a){
if (inOrder(a) == true) return; // previously missing
boolean flag = false;Here, an empty return statement functions similarly to a break statement in a loop. With this implementation, bogosort will recognize if it is given a sorted array and will terminate if that is the case.
On the other hand, the first implementation doesn’t particularly care if it is given an ordered array. It will immediately jump into the while loop, randomizing and checking for order.
However, there is yet another way to implement an inOrder check for the unadulterated input — putting it at the start of the loop:
public static void bogoSort(int[]a){
boolean flag = false;
while (!flag){
if (inOrder(a)) return; // check built into loop
// randomize
flag = inOrder(a);
}This method might seem quite a bit more inefficient, since an additional inOrder call means an additional O(n) being tagged onto the runtime, but with n! in the picture, and big O dropping coefficients, there ends up being no meaningful difference.
Knowing these small discrepancies between implementations, what’s the difference in big O runtime? Before we start making any calculations, let’s attribute some roman numerals to the three different implementations. The first one (which does not check for order in its input) will be referred to as I. The second (which checks for order in its input once) will be referred to as II. The third (which checks for order in its input once, and then continues to check it with each loop iteration) will be referred to as III.
Looking at bogosort I, we see that there are two pieces of code that cause array accesses, the most expensive operation that we’ll be considering for our big O calculation. First, there is the swap operation, which may initially seem like it takes O(n) time complexity, but is actually far more inefficient. This is because the for loop that makes calls to the swap method is wrapped in the while loop that checks for the ordered status of the array. This means that the swap operation is associated with a time complexity of O(n!), on account of the total number of possible permutations of the given array. This also brings us to the second piece of code that performs array accesses, and that’s the call to inOrder, which in the worst case scenario (big O forms upper bounds) will take O(n-1) time, which can simply be reduced to O(n).
You might have noticed that the O(n!) time complexity of the swap calls actually isn’t entirely accurate. After all, the swap function makes many more array accesses than our calculation of O(n!) implies. But this statement of inaccuracy can also be said about our big O calculation for inOrder, which takes O(n-1) time, but is reduced to O(n), since big O drops insignificant terms and coefficients — hence the O(n!) time complexity for the randomized sorting that bogosort does. This leaves us with a big O running time of O(n!*n) for bogosort I.
Next, let’s take a look at bogosort II, which is very similar. In fact, the only difference between bogosort I and II is that the latter has an inOrder check before the while loop. Since the call to inOrder is outside the while loop and is, therefore, independent from the permutations that bogosort goes through, it ends up being an addition to the big O calculation, not a multiplication. In other words, this call to inOrder occurs once every call to bogosort II, while the call to inOrder within the while loop occurs for each time the while loop runs. If something runs for each time of something else, then you know that it involves multiplication. The same logic can be applied to calculating the number of permutations there are for an array. For example, we know the number of permutations of an array of length 7 to be 7!, but how is this value calculated? Let’s imagine that a new, empty array of length 7 is created. In this array, we’ll test out different permutations of our data set. In the first slot, we have 7 options. We write down 7 in our notes. We move to the next slot. Knowing that one of our options has been removed, we now have 6 options to choose from. So we write down 6. Hold on. What goes between the 7 and the 6? A multiplication symbol, of course! If you think about how permutations are formed, each slot’s number of options is for each of the previous options. In this case, there are 6 options for each of the 7 options, which means we have to multiply the two. Moving another slot ahead, we’ve used up another option, meaning we have to multiply 5 by our current product, and so on and so forth. This is where the factorial (!) comes from.
So the big O of bogosort II is not very different from bogosort I, and after reduction, you’ll see that it’s exactly the same. We know that part of our big O calculation will be O(n!*n), but we also have to tag on O(n) for the one extra call to inOrder, so we have O(n!*n+n). But that isn’t our final answer, since O(n) is completely insignificant when compared to the magnitude of a factorial term. Our final big O running time for bogosort II is O(n!*n).
Lastly, we have bogosort III’s big O to look at (I have a sneaking suspicion that the big O running time is going to be the same as the previous ones…). The only difference between bogosort III and I is that the former has an additional inOrder check in the while loop. Since a single inOrder call in the while loop multiplies n by n!, adding another n just means we’ll get O(n!*2n), which can be simplified to O(n!*n). In fact, this coefficient drop was done for all the big O calculations for the previous bogosort implementations as well — all of the array accesses conducted by swap simply multiply n by some constant, which we’ll call z. We’ll end up with O(n!*zn) which drops the coefficient z to make O(n!*n) for our big O running time of bogosort III.
After looking at all three implementations of bogosort and finding no meaningful running time differences between them, we can conclude that bogosort is the least efficient running algorithm, right? How can we beat O(n!*n)?
Bogobogosort
I think you already know where this is going. Bogobogosort, which I’ll refer to as BBS for simplicity’s sake, is a recursive version of bogosort that turns an already inefficient sorting algorithm into an even more inefficient sorting algorithm. There are a few different ways to implement bogobogosort, all of which are wildly inefficient. Here are just a few:
- Progressively bogosort larger and larger subsets of the data set until the data set itself is sorted: Given an array {1, 2, 3, 4, 5} for example, bogosort {1}, then bogosort {1, 2}, then bogosort {1, 2, 3}, then bogosort {1, 2, 3, 4}, and finally bogosort {1, 2, 3, 4, 5}. The way this bogobogosort designed isn’t even logically sound (well, why would it be?), since the bogosorts of smaller subsets don’t even help the final bogosort to finish any faster. After all, that final bogosort is the only one that matters — all of the bogosorts of the previous subsets are just there to stall the running time essentially.
- Progressively bogosort larger and larger subsets of the data set until the data set itself is sorted, BUT, start over if the data being sorted is out of order at any point: Okay, this one is pretty bad. This algorithm will constantly be making calls to a function like inOrder throughout its inefficient sorting process and the fact that it restarts so frequently makes it terribly slow. To clarify, the bogosorting only resets if the data being sorted is out of order at any point. If the bogosorting were to restart for the entire data set being out of order, the algorithm would never finish for any out-of-order inputs of size 2 or larger.
- Esoteric bogobogosort: https://www.dangermouse.net/esoteric/bogobogosort.html I’d strongly recommend giving this a read; the algorithm didn’t even finish for a data set of size 7!
As a challenge, try calculating the big O of all of these bogobogosorts! The esoteric bogobogosort link has quite a bit of math on its page that you can use for inspiration. After finding the big O for bogobogosort, you’ll soon realize why people say it won’t finish for any sizable list before the heat death of the universe, which is about 10¹⁰⁰ years.
We’re not done de-optimizing our sorting algorithms, however. For the next few sorting “algorithms,” we might have to bend the rules a little bit.
Sorting with alpha particles, intrinsic order, and destroying the universe
Now this is where it gets exciting. These upcoming sorting algorithms are quite a bit harder to implement than your average bogosort. First, we have Miracle Sort (I think all of these deserve to be capitalized :)).
Miracle Sort
Miracle Sort is exactly as its name implies. First, check the data set’s ordered status. If it’s not in order, wait a bit. Then check again. Repeat.
At first glance, it seems like Miracle Sort just won’t work for any unordered data set, but that’s not necessarily true. Miracle Sort doesn’t do the sorting through code, or what we can call software. Miracle Sort relies on the hardware to do the sorting. Computers aren’t completely static — alpha particles flipping bits in the memory chips should eventually result in a successful sort. In other words, if a semiconductor memory chip runs into an ionizing particle, it’s possible that the chip’s state is altered, and thus, the data is altered. In theory, enough of these events should lead to the data getting sorted.
Intelligent Design Sort
Next up, we have another silly sort that would never be implemented in any practical scenario. This sorting algorithm is based on the theory of intelligent design, which states that the universe/life could not have arisen by chance, and instead were created by some intelligent entity with clear intentions to do so.
Though the chance of an array to be sorted is miniscule (1/n! to be precise), that chance aligns with our mere mortal understanding of “sorted.” The chance of this is so small that there must be some intelligent Sorter that constructed the list in such a way intentionally. In fact, the list is already sorted, but just in a way that our simply human minds cannot comprehend. Therefore, the data is already optimally sorted in some way that transcends our small brains and any attempt to change the order of that list to conform with our preconceived notions of what is “sorted” would actually make it less sorted.
Funnily enough, Intelligent Design Sort is both very efficient and horribly inefficient. By its own standards, it is completely optimal, taking O(1) time and sorting in-place, thus requiring no additional memory allocation. However, by our own sorting standards, it takes O(∞) time, as unordered data sets will never get sorted by the algorithm. The code for Intelligent Design Sort wouldn’t really be code at all. It’s up to the higher being(s) after all. Us mere humans know nothing about what “sorted” means.
An Everettian Sorting (AKA Quantum Bogosort)
There is another way to reach O(∞) running time and it delves a little bit into quantum theory. This “sort” is based on the Everettian interpretation of quantum mechanics, and this is only “possible” knowing that a classical computer is a quantum system.
First, the array is randomized. We check for order. If it isn’t in order, we destroy the universe.
If we’re lucky, then we’re in the universe in which the data set is sorted, and thus, the check for order only occurs once, and the algorithm is finished. If we’re unlucky, then we’re in a universe in which the data set is not sorted, so the universe is destroyed. As a result, the algorithm ends up taking all the time in the world, or big O running time of O(∞). The algorithm precisely ends as time itself ceases to exist.
Now that’s pretty cool. Or at least I think so.
References
https://en.wikipedia.org/wiki/Time_complexity
https://medium.com/@aryamurali/embed-code-in-medium-e95b839cfdda
