sorting strings

[Rev. Joseph Miklojcik]

[ 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 at dot.unipress.com