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

Question

Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness.

One can see that inserting elements of an array into a binary search tree and reading them back out requires (on insertion) the same comparisons as running Quicksort on that array. The sequence of pivots that Quicksort uses is the sequence of insertions into the binary search tree.

This is also trivially true for Heapsort and heaps, since Heapsort is literally doing such a series of insertions and then reading the elements back out.

Does there exist an analog of this in the case of, say, Mergesort? Is there a deeper connection here, or is it an interesting coincidence between data structures and sorting algorithms?

Answer 1

The Bentley-Saxe logarithmic method can sort a set in $O(n \lg n)$ time by merging sorted lists of equal size, much like merge sort.