Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!rpi!uwm.edu!rutgers!aramis.rutgers.edu!topaz.rutgers.edu!jmik From: jmik@topaz.rutgers.edu (Rev. Joseph Miklojcik) Newsgroups: comp.lang.c Subject: Re: sorting strings Keywords: sort, string Message-ID: Date: 20 Nov 89 22:44:59 GMT References: <4496@blake.acs.washington.edu> Distribution: usa Organization: Rutgers Univ., New Brunswick, N.J. Lines: 26 To: jimmy@blake.acs.washington.edu [ I haven't read too far ahead in this group, so this may be redundant information. Bear with me. ] > I want to sort 10000 records, each of 80 bytes long, in ascending order. If you trust qsort(), it's a clear win. It is possible that qsort() right off the shelf may not use an efficent partitioning method, and may recurse on small sublists. This could make it worse than the other D&C sorts you mention. Even if you don't trust the c library qsort(), implementing your own is still a good idea if you are after pure speed. The quicksort algorithm only stacks indicies (rather than mergesort which stacks sublists), which will cause minimal paging. And it's faster than anything we can draw a lower bound on. If you do have problems with thrashing on whatever machine you are using, you might consider heapsort, which is entirely in-place. But I doubt that should be necessary. If you do end up implementing your own qsort, the textbook for my algorithm class has a very comprehensive list of tricks you can use to make qsort work better. "Computer Algorithms; Introduction to Design and Analysis", 2nd edition, Saara Baase, Addison Wesley, Reading MASS. (hope this helps) --joe joe@dot.unipress.com