Demon Sort

Introduction

Demon sort is a sorting algorithm that violates the second law of thermodynamics. It is based on the idea of Maxwell's Demon, the central character in a thought experiment devised by the great 19th century physicist James Clerk Maxwell.

Algorithm Description

Produce a gas in which the molecular speed of each molecule is proportional to the value of one of the numbers to be sorted. Place the gas in a container with a barrier dividing it into two sections, A and B. The barrier should have a hole small enough to allow one molecule at a time pass through it, and the hole should have a door operated by a demon. The demon can then open the hole when spotting a fast molecule approaching from side A or a slow molecule from side B, and close it if a slow molecule approaches from side A or a fast one from side B.

Over time, all molecules slower than the threshold will be on side A, and all faster will be on side B. This has sorted the numbers into those less than a certain value and those larger than the same value.

If either side of the container contains more than one molecule, partition it with another barrier and demon, and apply the algorithm recursively.

When all sections of the container have only one molecule, read off their speeds in order to give the sorted list of numbers.

Analysis

If there are n molecules to be sorted, it will require on average n! molecule-door collisions to allow all the "slow" molecules to pass through to the slow side and all the "fast" ones to pass in the other direction.

This procedure must then be carried out for each half of the molecules, recursively, so we need to add (n/2)! collisions (just one times this, since the two subsets can be performed in parallel).

We can see that the total complexity of the algorithm is O(n! + (n/2)! + (n/4)! + (n/8)! + ... + 1!). There are log₂ n terms in this sum, but each is smaller by a factor of 2. I think this makes the overal complexity O(n! log(log n)), but I could be wrong...*

However, this algorithm not only sorts the list of numbers into numerical order, it produces a temperature gradient across the sections of the container, from cold to hot, from an initial uniform temperature, without doing any work. This temperature gradient can be used to drive a heat engine, producing useful energy.

So besides being a practical sorting algorithm, demon sort is also a free energy generator. By using the energy generated to operate the computational device on which the demon sort algorithm runs, one produces a workable perpetual motion device!

*In fact, Mike Rosulek writes:

Demon sort is actually O(n!) instead of O(n! log log n). This can be seen by applying the master theorem for recurrences on T(n)=n!+T(n/2). See case 3 in Wikipedia's version. Even if the demon doesn't do both recursive cases in parallel (i.e., we have n!+2*T(n/2)), the factorial still overwhelms the running time.