9
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.