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:

1. Shuffle: Take the input array (or list) of elements and randomly shuffle them
2. Check: Check if the shuffled array is now magically in a sorted order
3. Repeat: If the list is not sorted, go back to step 1 and repeat the process

Notice that the only logic for sorting our items is in Step 1, where all of the items are randomly shuffled. This means that, at each step, there is no logical or deterministic way to figure out what the array will look like. Step 1, run multiple times on the same input, would likely result in the random arrangement of numbers being different each and every time. This is a huge departure from every other search algorithm we have looked at where there was a strategy involved that didn’t involve randomly shuffling the entire input.

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:

The only thing we know with certainty is that all of the items will eventually be shuffled in a way where they end up being sorted. The thing we don’t know is how long that will take. It could be done quickly or it could take forever! Because of this unpredictability, Bogosort isn’t meant to be used in any real-world scenario outside of comical academic exercises.

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

The average case time complexity of Bogosort is O(n!). This stems from the fact that, on average, it will take n! (n factorial) random shuffles to stumble upon the correct sorted permutation. Factorial growth is incredibly fast...which means our algorithm will run incredibly slow:

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.

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, 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! 😇