Bei diesem Verfahren handelt es sich nicht wirklich um Mergesort, sondern um eines das Mergesort sehr nahe kommt.
Man hat eine Datenmenge in vielen kleinen sortierten Dateien stehen und möchte diese Dateien zu einer großen Datei zusammenfügen (Combine-Schritt von Mergesort).
In den Heap wird jeweils das erste Element aus jeder Datei aufgenommen.
Da die Dateien sortiert sind, kann durch Ausgeben der Wurzel das
kleinste Element ermittelt werden.
Der Heap wird nun nicht wie gewöhnlich verkleinert, sondern behält
(zunächst) seine Anzahl an Knoten bei, in dem das „gelöschte“ Element
durch seinen Nachfolger in der Datei, aus der es stammt, ersetzt
wird.
Mit „siftdown“ muss die Heap-Eigenschaft möglicherweise
korrigiert werden.
Das Verfahren wird solange wiederholt, bis alle Element sortiert in einer neuen Datei stehen.