Summary

Bogobogo Sort is a recursive, "generate and test" algorithm that stands as one of the most inefficient sorting methods ever conceived. It is a variation of Bogo Sort but with a far more complex termination condition. To sort a list, it first recursively sorts the initial n-1 elements. Then, it checks if the last element is in the correct place. If not, it shuffles the entire list and starts over. The "is sorted" check is itself a recursive sorting process, leading to its factorial-of-a-factorial average time complexity.

How it Works

• 1. Make a Copy: To check if a list is sorted, first create a complete copy of it.

• 2. Recursively Sort Sublist: Sort the first n-1 elements of the copy using Bogobogo Sort. This is the first layer of recursion.

• 3. Check Final Element: Check if the nth element of the now partially-sorted copy is greater than the (n-1)th element. If not, randomize the order of the elements in the copy and repeat step 2.

• 4. Final Comparison: Once the copy is fully sorted according to the rules above, check if it is now identical to the original list. If it is, the original list is considered sorted. If not, the original list is shuffled, and the entire 4-step process begins again.