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

Proszę wybaczyć zwięzłość tytułu, mogłem poświęcić jasność na ołtarzu zwięzłości.

Widać, że wstawienie elementów tablicy do binarnego drzewa wyszukiwania i ich ponowne odczytanie wymaga (przy wstawianiu) takich samych porównań, jak uruchomienie Quicksort na tej tablicy. Sekwencja osi przestawnych używanych przez Quicksort to sekwencja wstawek do drzewa wyszukiwania binarnego.

Jest to również trywialnie prawdziwe w przypadku Heapsort i sterty, ponieważ Heapsort dosłownie robi taką serię wstawek, a następnie odczytuje elementy z powrotem.

Czy istnieje analog tego w przypadku powiedzmy Mergesort? Czy istnieje tutaj głębsze połączenie, czy może ciekawy zbieżność między strukturami danych a algorytmami sortowania?

Metoda logarytmiczna Bentley-Saxe może posortować zbiór$O(n \lg n)$ czas, łącząc posortowane listy o równej wielkości, podobnie jak sortowanie po scaleniu.