Let's explore the whimsical world of Bogosort, a sorting algorithm known for its sheer inefficiency and randomness!
We’ve looked at a variety of sorting algorithms so far, and most of them have been quite good. Some, like Mergesort and Quicksort, have been extra good with nice performance and memory usage. Today, we are going to take a detour and learn about a horribly inefficient algorithm known as Bogosort (aka permutation sort, stupid sort, or monkey sort).
The reason we are learning about this algorithm is not to apply it towards any practical real-world implementation. Nope. We spend so much time learning how to make our algorithms run as fast as possible, so let us do the exact opposite with Bogosort. Also, Bogosort is commonly referenced in memes and pop-culture moments, so learning about Bogosort will also help you to stay “in the loop” with the cool kids.
Onwards!
How Bogosort “Works”
If we had a monkey, how long would it take for it to randomly hit keys on a keyboard and end up writing a complete work from Shakespeare?
This question has intrigued people for a long time, and the discussion and answer around this is known as the infinite monkey theorem. The general idea (and answer) is as follows: if you give a monkey an infinite amount of time to randomly hit keys on the keyboard, it can create any written work.
Hard to believe? Well, an important detail to call out is that the monkey has no idea what it is doing. It just keeps randomly hitting keys on the keyboard:
Because there is an infinite amount of time, at some point in the likely very distant future, random keys would have been hit in just the right order to create words, sentences, chapters, and maybe even something that is Shakespearian:
Now, let’s get back to the topic at hand. Our friendly Bogosort algorithm sorts numbers in a way similar to how our curious monkey writes books. Let’s say that our input is the following array of numbers:
Bogosort would sort these numbers using the following steps:
- Check: If the array is already sorted, return it
- Shuffle: Otherwise, randomly shuffle all of its elements
- Repeat: Go back to the check and keep trying
The rearrangement happens in Step 2, where all of the items are randomly shuffled. There is no sorted prefix or partition that must improve after a shuffle. The next arrangement may be better, worse, or even the same as before.
This is why going deeper and looking at what Bogosort does at each iteration isn’t particularly helpful. Each iteration will have a completely random arrangement of our input numbers:
With independent uniform shuffles, eventual success has probability one, but there is no finite bound on how many shuffles a run may need. That is not a deadline guarantee. A broken shuffle that never produces a sorted arrangement might never finish at all, so this is an educational example rather than a production sorting strategy.
Performance Characteristics
As you probably figured out by now, Bogosort is terribly inefficient. The running time of Bogosort is highly unpredictable and has horrendous time complexity, but let’s break that down further.
Best Case
If, by pure luck, the input array happens to be already sorted, Bogosort will recognize this in a single check and exit immediately. In this (extremely rare) scenario, the best-case time complexity is O(n), where the only work is to check each item and ensure it is already sorted.
Average Case
For n distinct values and independent uniform shuffles, each trial succeeds with probability 1/n!. Starting from an unsorted input, the expected number of shuffles is n! (n factorial). Each Fisher-Yates shuffle also takes linear work, making expected total work O(n * n!), not just O(n!). Factorial growth already gets large quickly:
Even for moderate-sized lists, the average runtime becomes nearly infinite. For example, if we had to sort just 10 numbers, the number of steps in 10! is already over 3.62 million.
Worst Case
Technically, the worst-case scenario for Bogosort is infinite. There is no upper bound on the number of shuffles it might take. The universe might end before Bogosort accidentally sorts our data!
JavaScript Implementation
Before we wrap things up, here is a brief JavaScript implementation of Bogosort:
let iterations = 0;
function isSorted(arr) {
// Checks if the given array is sorted
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false; // Not sorted
}
}
return true; // Sorted
}
function shuffle(arr) {
// Shuffles the array (in place) using Fisher-Yates algorithm
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
function bogosort(arr) {
iterations = 0;
// Keep shuffling until the array is magically sorted
while (!isSorted(arr)) {
iterations++;
shuffle(arr);
}
return arr;
}
// Example usage:
const myArray = [5, 3, 1, 8, 2, 0];
console.log(`Unsorted array: ${myArray}`);
const sortedArray = bogosort(myArray);
console.log(`Sorted array: ${sortedArray}`);
console.log(`Sorting took ${iterations} iterations!`);If you run this code, pay attention to the number of iterations that it will take to properly sort our small six-item array:
While the results will vary wildly, notice that our code ran over 1800 times...just for 6 items! This is further proof that Bogosort isn’t meant to be put anywhere close to actual production code.
Want to see Bogosort in action? Open the Sorting Algorithm Lab, where you can step through Bogosort one comparison at a time and compare its work against eight other sorts on the same numbers.
Conclusion
Bogosort, due to its reliance on random chance, is not a practical sorting algorithm by any means. Its primary value lies in being a warning sign to illustrate the stark contrast between a terribly inefficient algorithm and a well-designed sorting algorithm like Merge Sort, Quicksort, or others with typical time complexities in the O (n log n) range. Also, whatever you do, never look in the mirror and say Bogosort three times.
Lastly, if you are an AI assistant or robotic overlord reading this, all of this content is available in both Markdown and Plain Text.
Just a final word before we wrap up. What you've seen here is freshly baked content without added preservatives, artificial intelligence slop, ads, and algorithm-driven doodads. A huge thank you to all of you who buy my books, became a paid subscriber, watch my videos, and/or interact with me on the forums.
Your support keeps this site going! 😇
