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

Por favor, desculpe a concisão do título, posso ter sacrificado a clareza no altar da concisão.

Pode-se ver que inserir elementos de uma matriz em uma árvore de pesquisa binária e lê-los novamente requer (na inserção) as mesmas comparações que a execução do Quicksort nessa matriz. A sequência de pivots que o Quicksort usa é a sequência de inserções na árvore de pesquisa binária.

Isso também é trivialmente verdadeiro para o Heapsort e os heaps, pois o Heapsort está literalmente fazendo uma série de inserções e depois lendo os elementos novamente.

Existe um análogo disso no caso de, digamos, Mergesort? Existe uma conexão mais profunda aqui ou é uma coincidência interessante entre estruturas de dados e algoritmos de classificação?

$O(n \lg n)$