I recently decided to think of an algorithm based on DNA mutations. Being unclear about its speed complexity, I decided to write it up and test it out. The result was counter intuitive.

First, a simpler variant: Imagine the following sorting algorithm, given an array of numbers: Randomly shuffle the numbers until they are sorted.

What is the median amount of times you end up shuffling the array before it is sorted?

The answer is n! where n is length of the array. This is known as Bogosort.

Now, a slightly more advanced version:

Assume you can tell which numbers are already in their correctly sorted position, and which aren’t. Only randomly shuffle the numbers which are not yet sorted. Keep all the others in place.

What is the median amount of times you end up doing this kind of shuffling before the whole array is sorted?

I’ll be revealing the answer tomorrow.