<p><a href="https://cstheory.stackexchange.com/questions/7642/i-dreamt-of-a-data-structure-does-it-exist">The Bentley-Saxe logarithmic method</a> can sort a set in $O(n \lg n)$ time by merging sorted lists of equal size, much like merge sort.</p>

CC BY-SA 3.0
2013-04-14T17:32:07.667Z
2013-04-14T17:32:07.667Z
2017-04-13T12:32:28.117Z
jbapple
<p>Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness.</p>

<p>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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2013-04-14T08:47:06.503Z
There is a similarity between (adaptive) MergeSort and the use of a Wavelet Tree, see http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=39E5D34004409AF7E7743678DC1B13F5?doi=10.1.1.144.1191
J.y B.y
<ds.algorithms><ds.data-structures><sorting>
Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?
Federico Lebrón
# Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?

(Asked by: username_0 on 2013-04-13)

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?

**Tags:** ds.algorithms, ds.data-structures, sorting
> **Comments:**
> **username_1**: There is a similarity between (adaptive) MergeSort and the use of a Wavelet Tree, see http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=39E5D34004409AF7E7743678DC1B13F5?doi=10.1.1.144.1191  

---

## 1 answers

### Answer by username_2 on 2013-04-14. Score: 5 | Accepted answer

[The Bentley-Saxe logarithmic method](https://cstheory.stackexchange.com/questions/7642/i-dreamt-of-a-data-structure-does-it-exist) can sort a set in $O(n \lg n)$ time by merging sorted lists of equal size, much like merge sort.


---

