No Free Input Buffer repeat kWayMerge; wait for input/output to complete; add new input buffer (if any) to queue for its run; determine run that will exhaust first; if (there is more input from this run) initiate read of next block for this run; initiate write of active output buffer; activeOutputBuffer = 1 – activeOutputBuffer; until end-of-run key merged; Exactly k + 1 buffer loads in memory.
{}