Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!pa.dec.com!bacchus!mwm From: mwm@pa.dec.com (Mike (My Watch Has Windows) Meyer) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: Date: 18 Jun 91 19:19:13 GMT References: <8235@oasys.dt.navy.mil> <1991Jun13.175106.6902@unislc.uucp> <8454@oasys.dt.navy.mil> <91169.133303GUTEST8@cc1.kuleuven.ac.be> Sender: news@pa.dec.com (News) Organization: Missionaria Phonibalonica Lines: 34 In-Reply-To: nj@magnolia.Berkeley.EDU's message of 18 Jun 91 18:12:31 GMT In article nj@magnolia.Berkeley.EDU (Narciso Jaramillo) writes: 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). Actually, the radix sort assumption is slightly more general than that. It assumes that you can address "subkeys" that are small enough to be bucket sorted on your machine. This assumption is true for any octet addressable machine with more than a few K octets of ram. Note that a fully general implementation inside of those constraints requires that you allow specification of the order to sort subkeys (e.g. - byte 3, then byte 1, then byte 2, then byte 0), as well as an ordering on each subkey (e.g. - for each subkey, you provide a lookup table that gives the sort order for that subkey).