Bogobogosort

Introduction

Bogobogosort is a sorting algorithm based on the popular bogosort algorithm.

Algorithm Description

To understand bogobogosort, it is necessary to first have an understanding of the finer points of bogosort.

Bogosort can be described as follows:

Check if your list of number is sorted. If so, stop. If not, go to step 2.
Rearrange the list of numbers randomly.
Go to step 1.

Bogosort is normally characterised as O(n × n!). Step 1, the checking if the list is sorted, is assumed to be done with some sort of efficient one-pass comparison check, which takes n-1 operations. The loop will repeat on average n! times, since this is the number of permutations of n objects. The product (n-1)n! is O(n × n!).

This is far too efficient.

Bogobogosort specifies how one should check if the list of numbers is sorted. It does it recursively, because as anyone who knows anything at all about computer science knows, recursion is always good and cool. To check if the list is sorted, use the following procedure:

Make a copy of the list of numbers.
Sort the first n-1 elements of the copy using bogobogosort.
Check to see if the nth element of the sorted copy is greater than the highest element of the first n-1 elements. If so, the copy is now sorted, else randomise the order of the elements of the copy and go to step 2.
Check to see if the copy is in the same order as the original list.

Analysis

Lordy, I dunno. I'm guessing this thing is at least O(n!^n!).

Bogobogosort was implemented in C++ and timing runs made for sorting n numbers, averaged over 20 trials:

n Time (seconds)

1 0.0000

2 0.0000

3 0.0008

4 0.0054

5 0.0745

6 450

7 run overnight, did not finish

n	Time (seconds)
1	0.0000
2	0.0000
3	0.0008
4	0.0054
5	0.0745
6	450
7	run overnight, did not finish

Mike Rosulek writes:

I believe bogobogosort is O(n * (n!)ⁿ).
Let BBS(n) be the expected time of bogobogosort on input size n, and SC(n) the expected time of the sort checking algorithm on input size n. Then
BBS(n) = SC(n) + (1 - 1/n!) BBS(n)
// with probability 1/n!, we finish, otherwise repeat BBS(n)

SC(n) = O(n) + BBS(n-1) + (1-1/n)( BBS(n-1) + O(n) )
// with probability 1/n, the n-th guy is the largest, otherwise must shuffle and re-sort the first n-1 guys
Then substituting in for SC (skipping some simplifications - the (1-1/n)*O(n) factor gets swallowed by the first O(n)):
BBS(n) = O(n) + BBS(n-1) + (1-1/n) BBS(n-1) + (1-1/n!) BBS(n)
// multiply by n!
n! * BBS(n) = O(n*n!) + n! ( BBS(n) + 2 BBS(n-1) ) - BBS(n) - (n-1)!*BBS(n-1)
// rearrange
BBS(n) = O(n*n!) + (2n! - (n-1)!)BBS(n-1)
= O(n*n!) + O(n!) * BBS(n-1)
= O(n*n!) + O(n*(n!)²) + ... + O(n*(n!)ⁿ)
= O(n*(n!)ⁿ)

Nathan Collins, on the other hand, writes:

Let B(n) be the time complexity of bogobogosort on an input of size n. From the original analysis of bogosort we expect to try n! times before the random shuffle sorts the list. So,
B(n) ≤ n!*(Copy(n) + Check(n) + Randomize(n))
Making a copy of the list is O(n) (assuming the size of the numbers is bounded). To randomize, you can drop all the numbers on the floor. Dropping them is O(1), and it takes O(n) to pick them up and put them back in the computer (assuming you only have O(1) many hands).
To check if the original list is sorted we need to bogobogosort the first n-1 elements of the copy, and then see if the last element of the copy is at least as large as the n-1st. If the nth element of the copy isn't maximal we need to randomize the copy again. And, finally, when we have managed to sort the copy, we need to compare it to the original list. So, since the chance that the last element is maximal is at least 1/n, we have:
Check(n) ≤ n*(B(n-1) + Max(2) + Randomize(n)) + Compare(n)
giving
B(n) ≤ n!*(Copy(n) + (n*(B(n-1) + Max(2) + Randomize(n)) + Compare(n)) + Randomize(n))
Comparing the two n-element lists is O(n), so we have
B(n) ≤ n!*(O(n) + (n*(B(n-1) + O(1) + O(n)) + O(n)) + O(n))
= n!*(O(n) + n*(B(n-1) + O(n)))
= n!*(n*(B(n-1) + O(1) + O(n))
= n!*(n*(B(n-1) + n*O(1)))
using O(n) = n*O(1) and O(1) + O(n) = O(n). Expanding B(n-1) recursively we get
B(n) = n!*n²*O(1) + n!*n²*(n-1)!*(n-1)²*O(1)
+ n!*n²*(n-1)!*(n-1)²*(n-2)!*(n-2)²*O(1) + ...
+ n!*n²*(n-1)!*(n-1)²*(n-2)!*(n-2)²*...*2!2²*1!*1²*O(1)
Now, the constant O(1) is the same for all terms above, and the nth term bounds the first n-1 terms. So, replacing with the last term throughout, we get
B(n) ≤ n*n!*n²*(n-1)!*(n-1)²*(n-2)!*(n-2)²*...*2!2²*1!*1²*O(1)
= n!*n!*n!*n!*(n-2)!*(n-3)!*...*4!*3!*O(1)
by folding the square terms and the leading n into the smaller factorials, and absorbing a 2 into the constant. So
B(n) = O(n!*n!*n!*n!*(n-2)!*(n-3)!*...*(k+1)!)
where k is any fixed number and we have absorbed factorials less than (k+1)! into the constant. Noting that we could bound each (n-j)! by n! we can simplify the bound to B(n) = O(n!^n-k), for any fixed k.
Now O(n!^n-k) is much better than your guess of O(n!^n!), making bogobogosort even more attractive.