Eine Mehrwegezusammenführung ist im Allgemeinen besser. Betrachten Sie drei kleine Dateien:
%Vor%und
%Vor%und schließlich
%Vor% Wenn Sie eine Zusammenführung mit a und b vornehmen, bleibt uns (sagen wir)
und
%Vor% Eine endgültige Zusammenführung würde die sortierte Liste erstellen, aber beachten Sie, dass wir in dieser endgültigen Zusammenführung die Elemente a und b erneut aufrufen müssen. Es ist diese Wiedervereinigung, die bei der Kaskadierung von Zweiwege-Verschmelzungen verschwenderisch ist.
Was Sie stattdessen tun können, ist eine einzelne Mehrwege-Zusammenführung. Seien Sie jedoch vorsichtig, wie Sie es tun. Vermeiden Sie insbesondere die naive Doppelschleife, die jeden Cursor scannt, um zu sehen, welcher Wert den Mindestwert hat. Verwenden Sie stattdessen einen Min-Heap. Dies bringt die Komplexität zurück auf O(n log n) .
Tags und Links algorithm mergesort external-sorting