Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!ysub!psuvm!blekul11!gutest8 From: GUTEST8@cc1.kuleuven.ac.be (Ives Aerts) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: <91169.133303GUTEST8@cc1.kuleuven.ac.be> Date: 18 Jun 91 13:31:03 GMT References: <8235@oasys.dt.navy.mil> <1991Jun13.175106.6902@unislc.uucp> <8454@oasys.dt.navy.mil> Organization: K.U.Leuven - Academic Computing Center Lines: 12 >> - There are no general purpose sorts which do better than O(n*logn). >False. See the above. It's a general purpose algorithm, and it's >always better (in the theoretical sense) than O(n*logn). 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) We have also seen the proof to this theorem but I'm not going to repeat it here since I forgot it :-) It has something to do with sort trees. 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)).