Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!swrinde!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!ucbvax!nj From: nj@magnolia.Berkeley.EDU (Narciso Jaramillo) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: Date: 18 Jun 91 18:12:31 GMT References: <8235@oasys.dt.navy.mil> <1991Jun13.175106.6902@unislc.uucp> <8454@oasys.dt.navy.mil> <91169.133303GUTEST8@cc1.kuleuven.ac.be> Sender: nobody@ucbvax.BERKELEY.EDU Organization: Postcarcinogenic Bliss, Inc. Lines: 18 In-reply-to: GUTEST8@cc1.kuleuven.ac.be's message of 18 Jun 91 13:31:03 GMT In article <91169.133303GUTEST8@cc1.kuleuven.ac.be> GUTEST8@cc1.kuleuven.ac.be (Ives Aerts) writes: We have seen this year (I just did my exam for it last week) that there is no GENERAL sorting algorithm which is better than O(n*logn) By GENERAL I mean that the algorithm must be able to sort anything (including things with variable length (which can of course be forced if you extend all items to the same maximum length)). To be more precise, the theorem holds only for algorithms which sort by comparing keys to each other. These algorithms rely only on the keys being linearly ordered, and the ability to do one comparison in O(1) time. Algorithms like Radix Sort make extra assumptions about the keys (in this case, that they are numbers and can be broken up into digits), and thus can achieve better worst case complexity (but at the cost of extra space utilization in this case). nj