# 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:

- Move only one disc at a time.
- Do not place a larger disc on top of a smaller disc.

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 2^{n}-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-2019, David Morgan-Mar. *dmm@dangermouse.net*

*Hosted by: DreamHost*