Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!aitken From: aitken@shamesh.cs.cornell.edu (William E. Aitken) Newsgroups: comp.lang.c Subject: Re: sort Message-ID: <29474@cornell.UUCP> Date: 29 Jun 89 17:53:48 GMT References: <166@stsim.UUCP> <4700040@m.cs.uiuc.edu> <1989Jun29.155648.28819@utzoo.uucp> Sender: nobody@cornell.UUCP Reply-To: aitken@cs.cornell.edu (William E. Aitken) Organization: Cornell Univ. CS Dept, Ithaca NY Lines: 20 In article <1989Jun29.155648.28819@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes: >In article <4700040@m.cs.uiuc.edu> kenny@m.cs.uiuc.edu writes: >>>Does anyone have a sort routine (in memory sort) faster than quicksort, of >>>so please e-mail it to me, thanks. >> >>Generally speaking, there isn't any; at least, no sort can be faster >>than quicksort by more than a constant factor on a von Neumann machine. > >There is an important phrase missing here: "in the worst case". There No. One of quicksort's problems is its horrendous worst case behavior : quadratic. It's rather easy to find sorts that are faster than quicksort in the worst case. Merge sort and Shell sort come to mind. William E. Aitken | On Earth it is considered {uw-beaver,rochester,decvax}!cornell!aitken | ill mannered to kill your Home: (607) 273-7810 Away : (607) 255-9206 | friends while commiting suicide ============================================*============= Avon ==============