## Aug 23 The Quantum Bogo Sort

With the demise of decision mathematics in the A level shuffle it's going to be sad to leave sorting algorithms behind, but here I present one of the crazier ones. The way we assess how good an algorithm is by how many operations it has to do on a list of n objects. The best conventional sorting algorithms such as quick sort and merge sort take nlog(n) time, with weaker ones like bubble sort taking n^2 time. n^2 is a bigger number of operations as n gets really big and so it is worse on average.

There is a cheaty quantum algorithm that relies on the many world interpreation of quantum theory that manages to get the complexity down to just n time. The quantum bogo sort looks like this:

Randomise the elements of the list.

Read each element in the list to check it is in order.

If not in order, then destroy the universe.

In all universes that survive you will have a sorted list. However the trick here is that you will never observe an unsorted list because you will only be able to make the observation in universes that survive. Notice that this is the best possible sorting algorithm because you have to have looked at each item in the list, so you can't do better than linear time.

Other ways to play around with this idea are gambling schemes. Imagine you take all of your life's savings and put them on a bet. It could be anything you like, so let's say you bet on a single number in roulette. If you win you can repeat as much as you like and if you lose you can commit suicide. You either end up with infinite resources or the neutral state of death.

Just a disclaimer, this is not life advice. Or not good life advice at the very least.