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

Veuillez excuser la justesse du titre, j'ai peut-être sacrifié la clarté sur l'autel de la concision.

On peut voir que l'insertion d'éléments d'un tableau dans une arborescence de recherche binaire et leur lecture nécessitent (lors de l'insertion) les mêmes comparaisons que l'exécution de Quicksort sur ce tableau. La séquence de pivots utilisée par Quicksort est la séquence d'insertions dans l'arbre de recherche binaire.

Cela est également trivialement vrai pour Heapsort et les tas, car Heapsort fait littéralement une telle série d'insertions puis relit les éléments.

Existe-t-il un analogue de cela dans le cas, par exemple, de Mergesort? Y a-t-il une connexion plus profonde ici, ou est-ce une coïncidence intéressante entre les structures de données et les algorithmes de tri?

$O(n \lg n)$