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

Perdone la brevedad del título, es posible que haya sacrificado la claridad en el altar de la concisión.

Se puede ver que insertar elementos de una matriz en un árbol de búsqueda binario y volver a leerlos requiere (al insertar) las mismas comparaciones que ejecutar Quicksort en esa matriz. La secuencia de pivotes que utiliza Quicksort es la secuencia de inserciones en el árbol de búsqueda binario.

Esto también es trivialmente cierto para Heapsort y montones, ya que Heapsort está literalmente haciendo una serie de inserciones y luego leyendo los elementos de nuevo.

¿Existe un análogo de esto en el caso de, digamos, Mergesort? ¿Existe una conexión más profunda aquí, o es una coincidencia interesante entre las estructuras de datos y los algoritmos de clasificación?

El método logarítmico de Bentley-Saxe puede ordenar un conjunto en tiempo fusionando listas ordenadas de igual tamaño, al igual que la ordenación por fusión.$O(n \lg n)$