Letter: To the nth degree

From Ben Laurie

Ian Stewart says that the simplest way to sort n things takes time
proportional to n2
(15 September, p 36).
Simplest, maybe, but not the
quickest. The quickest takes time proportional to n log(n).
There are several ways to achieve this, the best known being quicksort and
heapsort.

In fact, even this assumes you are using a machine with only one thread of
control. Scientific American (issue unknown, probably late 1970s or
early 1980s) published several unusual algorithms for doing things faster given
unconventional equipment. One of my favourites was a sorting method that worked
in linear time, using spaghetti. Here’s what you do:

a) For each number in your list, cut a piece of spaghetti to that length

b) Grab all your spaghetti

c) Flatten one end of the bundle against a table

d) Pick the highest piece off and measure it

e) Go to d

There was also a method for solving mazes in linear time—but I leave
that as an exercise for the reader.

London