# 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_{2} *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.

Home | Esoteric Programming Languages

*Last updated: Friday, 08 December, 2006; 00:09:39 PST.*

Copyright © 1990-2019, David Morgan-Mar. *dmm@dangermouse.net*

*Hosted by: DreamHost*