home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / sources / d / 1239 < prev    next >
Encoding:
Internet Message Format  |  1992-09-02  |  1.3 KB
  1. Xref: sparky comp.sources.d:1239 alt.sources.d:1091
  2. Path: sparky!uunet!sun-barr!ames!data.nas.nasa.gov!taligent!apple!voder!berlioz.nsc.com!desktop!nelson
  3. From: nelson@desktop.nsc.com (Taed Nelson)
  4. Newsgroups: comp.sources.d,alt.sources.d
  5. Subject: Re: Sorting in Virtual Memory
  6. Message-ID: <1992Sep2.182938.3974@berlioz.nsc.com>
  7. Date: 2 Sep 92 18:29:38 GMT
  8. References: <1992Aug27.093506.11349@sniap.mchp.sni.de> <1992Aug27.201457.26498@dcatlas.dot.gov>
  9. Sender: news@berlioz.nsc.com (UseNet News account)
  10. Organization: Applications Technology, National Semiconductor (Santa Clara, CA)
  11. Lines: 18
  12.  
  13. frank@D012S436.sniap.mchp.sni.de () writes:
  14.  
  15. > I'm writing a program which needs to sort a large array 
  16. > parts of which are swapped in and out of memory (my own
  17. > implementation of a sort of VM).
  18.  
  19. [E-mail to the asker bounced.]
  20.  
  21. I have no proof, but after thinking about it, it seems to me that MERGESORT
  22.   would give you the best performance, ASSUMING that you can't get away with
  23.   a BUCKETSORT or a RADIXSORT (look those up if you don't know -- they are
  24.   order n, not the usual n-log-n).
  25.  
  26. The reason for this is that MERGESORT, for much of it's execution, is very
  27.   localized.  In fact, I would not be surprised if this were the optimum
  28.   sorting for your problem...
  29.  
  30. If you get a true answer, please post a summary!
  31.