Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!cs.utexas.edu!uunet!mcvax!hp4nl!orcenl!bengsig
From: bengsig@oracle.nl (Bjorn Engsig)
Newsgroups: comp.lang.c
Subject: Re: sort
Message-ID: <458.nlhp3@oracle.nl>
Date: 30 Jun 89 07:47:27 GMT
References: <166@stsim.UUCP> <4700040@m.cs.uiuc.edu> <1989Jun29.155648.28819@utzoo.uucp>
Reply-To: bengsig@oracle.nl (Bjorn Engsig)
Organization: ORACLE Europe, The Netherlands
Lines: 23

From article <1989Jun29.155648.28819@utzoo.uucp> by henry@utzoo.uucp (Henry Spencer):
|There
|are sort algorithms which are considerably better (linear rather than
|linear-log) in the *typical* case.  Or so I am told.

I simply couldn't resist this, although it has nothing at all to do with C.

A few years ago an article in either Comm. of the ACM or Scientific American
(I don't remember which), described the spaghetti sorter, which is linear in
time for any initial distribution.

You use a bunch of (unboiled) spaghettis, and cut them in length corresponding
to each of the elements you want to sort, this is of course linear in time.
You then hold all the spaghettis together and put them vertically on a table
(being worstly linear in time), and you can easily pick out the largest,
then the next to largest, etc., again linear in time.  As a result, you have
your data sorted in linear time!

Don't ask me how you implement this in C :-)
-- 
Bjorn Engsig, ORACLE Europe         \ /    "Hofstadter's Law:  It always takes
Path:   mcvax!orcenl!bengsig         X      longer than you expect, even if you
Domain: bengsig@oracle.nl           / \     take into account Hofstadter's Law"