Heapsort: Heaps = ~ Quicksort: BSTs = ~ Mergesort: ___?

Bitte entschuldigen Sie die Knappheit des Titels, ich habe möglicherweise Klarheit auf dem Altar der Prägnanz geopfert.

Man kann sehen, dass das Einfügen von Elementen eines Arrays in einen binären Suchbaum und das erneute Auslesen (beim Einfügen) dieselben Vergleiche erfordert wie das Ausführen von Quicksort auf diesem Array. Die von Quicksort verwendete Abfolge von Pivots ist die Abfolge von Einfügungen in den binären Suchbaum.

Dies gilt auch trivial für Heapsort und Heaps, da Heapsort buchstäblich eine solche Reihe von Einfügungen vornimmt und dann die Elemente wieder ausliest.

Gibt es ein Analogon dazu beispielsweise für Mergesort? Gibt es hier einen tieferen Zusammenhang oder ist es ein interessanter Zufall zwischen Datenstrukturen und Sortieralgorithmen?

Die logarithmische Bentley-Saxe-Methode kann eine Menge in -Zeit sortieren, indem sortierte Listen gleicher Größe zusammengeführt werden, ähnlich wie beim Zusammenführen.$O(n \lg n)$