Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!usc!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!haven.umd.edu!mimsy!oasys!tdsmith
From: tdsmith@oasys.dt.navy.mil (Timothy Smith)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Message-ID: <8235@oasys.dt.navy.mil>
Date: 6 Jun 91 18:21:13 GMT
References: <191d6f59.ARN12eb@pilhuhn.ka.sub.org> <193e8efd.ARN1453@pilhuhn.ka.sub.org>
Reply-To: tdsmith@oasys.dt.navy.mil (Timothy Smith)
Organization: David Taylor Research Center, Bethesda, MD
Lines: 12

In article <193e8efd.ARN1453@pilhuhn.ka.sub.org> hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) writes:
>Imagine that You have 50 States. Bucket sort means now sorting the letters
>according to the name of the State in one of 50 Boxes (or Buckets) labeled
>with the name of the State. Going once through the data costs O(n); adding
>an element to the head of the list costs O(1) -> You get linear (O(n)) running
>time.

What?  Start with an unsorted list of n objects (or pointers to objects,
same thing...)  Is there a sort algorithm which is o(n)?  If so, use
it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical!

Tim