Originally Posted by DGPickett

I suppose your could write a sort that used a tournament space as big as available ram to write temp files each with one sorted sequence, and then all the files can be merged by sort -m, or a tree of sort -m's, an always 2 pass sort.

The idea of the progressive merge sort was to live with the cache and RAM limits dynamically without knowing where they are. And in real life, sometimes the amount of available RAM or CACHE varies with other activities, so it is not good to have a fragile fit.

BTW, the tournament write can write strings far longer than the tournament table size. If the input was already sorted, it would be written as one string. You write the smallest item >= the last item written, so with random data, I am guessing a 64K leg tournament would write 96K items a sorted string, but my math is a bit weak. Someone show me up.

If you wanted to code it in a single process, you could write all sorted strings to one temp drive, write the starting offsets of each sorted string on a second temp file and fix the tournament size at something fitting comfortably within upper cache. The input file could be mmap()'s so actual records to be written are in RAM, just offsets in the tournament table. After the first pass, you know you have N strings to merge, so mmap() the output files and merge them. Since there are just 3 files open at a time, no fd limit woes. The mmap() lets your read from N different points in the first temp file. The one temp file write of all input data creates a huge change in working set size. Writing just one main file at a time minimizes write buffer cost. The original reading, although through mmap() page faults, is generally sequential. The second read uses just N-2N pages to buffer the sequential string reads. The latency is even pretty low, essentially 0 from last read to first write.