Hanoi Sort


Introduction

Hanoi sort is an O(exp(n)) (exponential time) sorting algorithm. It is based on the famous Tower of Hanoi puzzle. It has the interesting property that a list sorted in reverse order is sorted in linear time, while a list sorted in the correct order requires exponential time to confirm the ordering. This makes it an optimal sorting algorithm.

Algorithm Description

Treat the unsorted list of numbers as specifications for the radius of discs in a Tower of Hanoi problem. If the list contains non-positive numbers, simply add a constant k to each number to make them all positive.

Place the unsorted discs on one of the three Tower of Hanoi pegs, with the last number on the bottom, up to the first number on the top. Note that this may violate the traditional rules of the Tower of Hanoi, in that larger discs may appear on top of smaller ones.

Now proceed by moving discs from the original peg to one of the other two pegs, subject to the following rules:

When the entire stack of discs has been moved from the original peg on to one of the other pegs, the discs will have been sorted. Read the radius of the top disc, which will be the smallest number, and proceed down the stack to the bottom disc, representing the largest number. (If necessary, subtract the constant k to convert these back to the original numbers.)

Analysis

If the original list of numbers is already sorted, then moving the tower corresponds exactly to the classical Tower of Hanoi puzzle. It is well known that moving the tower to another peg require 2n-1 moves, therefore the algorithm completes in O(exp(n)) time.

If the original list of numbers is exactly in reverse order, the tower can be transferred simply by moving the top disc (the largest) to a new peg, then the next disc to the same peg, and so on to the last (smallest) disc. This takes exactly n moves, so in this case, Hanoi sort completes in O(n) time. This is the theoretical best limit that any sorting algorithm can achieve, and Hanoi sort manages it for the worst possible starting condition!

It is left as an exercise for the reader than in a random case, the complexity is also O(exp(n)).

However, application of Murphy's Law shows that when you want to sort a list of numbers, they will inevitably be in the worst possible arrangement; i.e. reverse order. This is precisely the ordering for which Hanoi sort achieves its best performance, and therefore Hanoi sort is an optimal sorting algorithm.


Home | Esoteric Programming Languages
Last updated: Tuesday, 29 August, 2006; 22:32:28 PDT.
Copyright © 1990-2017, David Morgan-Mar. dmm@dangermouse.net
Hosted by: DreamHost