# The devil

Bogosort, also known as stupid sort or monkey sort, is a rather (in)famous sorting technique known for its inefficiency. In bogosort, you shuffle the array randomly and check if it's sorted; if it isn't, you repeat the whole thing.

Since you're clever, you come up with a better version of bogosort. If some of the first and last few values (a prefix and a suffix of the array) are already correctly sorted, we don't need to include them in the shuffle; we can fix them in place. For example, suppose that we shuffle and get $$(1,2,6,4,5,3,7)$$; we can now fix the $$1,2,7$$ and only shuffle $$6,4,5,3$$. Note that although $$4,5$$ are in the correct place, we still include them in the shuffle since they are not "first and last few values".

Let $$X(n)$$ be the expected number of shuffles needed to sort the first $$n$$ natural numbers, given that none of the numbers are in the right place initially (so all numbers are included in the shuffle). If $$X(15)$$ can be written as $$\frac{A}{B}$$ where $$A$$ and $$B$$ are coprime positive integers, what is the value of $$A+B$$?

Bonus Question What is the expected running time of the modified bogosort?

×