Merging sorted runs using large main memory (Q1116703)

With large amounts of main memory, we show that the best method for merging sorted runs in almost all circumstances is to use two input buffers for each run. The use of these buffers makes it likely that reading in the sorted runs and writing the merged file overlap. We demonstrate that this method, with one or two passes, is superior to any merge pattern where reading and writing do ot overlap in almost all cases we are likely to encounter. We also show a pathological example, constructed from constraints on the method, where in spite of having two buffers for each run, some significant non-overlapping occurs.