English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the connections between sorting and the binary search tree (BST)model, with an aim towards showing that the fields are connected more deeplythan is currently appreciated. While any BST can be used to sort by insertingthe keys one-by-one, this is a very limited relationship and importantly saysnothing about parallel sorting. We show what we believe to be the first formalrelationship between the BST model and sorting. Namely, we show that a largeclass of sorting algorithms, which includes mergesort, quicksort, insertionsort, and almost every instance-optimal sorting algorithm, are equivalent incost to offline BST algorithms. Our main theoretical tool is the geometricinterpretation of the BST model introduced by Demaine et al., which finds anequivalence between searches on a BST and point sets in the plane satisfying acertain property. To give an example of the utility of our approach, weintroduce the log-interleave bound, a measure of the information-theoreticcomplexity of a permutation $\pi$, which is within a $\lg \lg n$ multiplicativefactor of a known lower bound in the BST model; we also devise a parallelsorting algorithm with polylogarithmic span that sorts a permutation $\pi$using comparisons proportional to its log-interleave bound. Our aforementionedresult on sorting and offline BST algorithms can be used to show existence ofan offline BST algorithm whose cost is within a constant factor of thelog-interleave bound of any permutation $\pi$.

The Geometry of Tree-Based Sorting