Re: big sort

[futrelle@ccs.neu.edu (Robert Futrelle)]

When sorting huge files, you may want to look at techniques
used in database systems in which the files are often larger
than will fit in memory.  Typically is such cases, pieces of the
files are sorted, written out and then merged.

Also, beware of inserting a single element and then resorting.
Some of the efficient techniques can't handle these simple cases
well (but insertion sort could).   The best techniques will never
perform better than NlgN. Also, do you want a stable sort or
not (my guess is that you don't)?

For references, see Salzberg's file structures book or the algorithm
books of Sedgewick or Cormen, et al.  

  Bob Futrelle
-- 
Prof. Robert P. Futrelle | Biological Knowledge Lab, College of CS
Office: (617)-373-2076   | Northeastern University, 161CN
Fax:    (617)-373-5121   | 360 Huntington Ave.
futrelle@ccs.neu.edu     | Boston, MA 02115