Heapsort: Heaps = ~ Быстрая сортировка: BSTs = ~ Mergesort: ___?

Прошу прощения за краткость названия, я, возможно, пожертвовал ясностью на алтаре краткости.

Можно видеть, что вставка элементов массива в двоичное дерево поиска и их повторное чтение требует (при вставке) тех же сравнений, что и запуск Quicksort для этого массива. Последовательность точек, которую использует Quicksort, - это последовательность вставок в двоичное дерево поиска.

Это также тривиально верно для Heapsort и куч, так как Heapsort буквально делает такую ​​серию вставок, а затем считывает элементы обратно.

Существует ли аналог этого в случае, скажем, Mergesort? Есть ли здесь более глубокая связь или это интересное совпадение между структурами данных и алгоритмами сортировки?

Логарифмический метод Бентли-Сакса может сортировать множество в$O(n \lg n)$ время слияния отсортированных списков одинакового размера, так же, как сортировка слиянием.