home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / c / 12377 < prev    next >
Encoding:
Text File  |  1992-08-15  |  1.5 KB  |  36 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!wupost!sdd.hp.com!nigel.msen.com!caen!nic.umass.edu!amherst!amhux1.amherst.edu!twpierce
  3. From: twpierce@amhux1.amherst.edu (Tim Pierce)
  4. Subject: Re: sort routines
  5. Message-ID: <1992Aug15.161911.28517@amhux2.amherst.edu>
  6. Sender: usenet@amhux2.amherst.edu (USENET News System)
  7. Nntp-Posting-Host: amhux1.amherst.edu
  8. Organization: Amherst College, Amherst MA
  9. References: <1992Aug13.170424@axion.bt.co.uk> <1992Aug13.181541.26041@news.uit.no>
  10. Date: Sat, 15 Aug 1992 16:19:11 GMT
  11. Lines: 23
  12.  
  13. In article <1992Aug13.181541.26041@news.uit.no> tomg@stud.cs.uit.no (Tom Grydeland) writes:
  14.  
  15. >As far as I know, the best solution for sorting a single linked list is the
  16. >mergesort. It's a recursion-based sorting which follows the general solution:
  17. >
  18. >0) If the list is just one element, it's sorted, return.
  19. >
  20. >1) If not, split your list in two approximately equal sublists.
  21. >
  22. >2) Mergesort (here's the recursion!) each one separately.
  23. >
  24. >3) Merge the two sorted sublists, and you have a sorted list to return.
  25.  
  26. An addendum: insertion and selection sort tend to work pretty well on
  27. very short lists (the cutoff is around seven-element lists, in my
  28. experience).  I've been able to improve recursive sorts from time to
  29. time by ending the recursion early and using one of these sorts for
  30. the last little bits.
  31.  
  32. -- 
  33. ____ Tim Pierce                / "Bisexual just means you pay for it."
  34. \  / twpierce@amherst.edu      /  
  35.  \/ (BITnet: TWPIERCE@AMHERST) /   -- Rock Hudson
  36.