Carnegie Mellon University<EMAIL_ADDRESS>Mellon University,
<EMAIL_ADDRESS>Guy E. Blelloch and Magdalen Dobson [500]Theory of
computation Sorting and searching

###### Acknowledgements.

We thank Kanat Tangwongsan for helpful discussions. We thank the anonymous
reviewers for their useful comments. This work was supported by the National
Science Foundation grants CCF-1901381, CCF-1910030, CCF-1919223, DGE1745016,
and DGE2140739.22

# The Geometry of Tree-Based Sorting

Guy E. Blelloch  Magdalen Dobson

###### Abstract

We study the connections between sorting and the binary search tree (BST)
model, with an aim towards showing that the fields are connected more deeply
than is currently appreciated. While any BST can be used to sort by inserting
the keys one-by-one, this is a very limited relationship and importantly says
nothing about parallel sorting. We show what we believe to be the first formal
relationship between the BST model and sorting. Namely, we show that a large
class of sorting algorithms, which includes mergesort, quicksort, insertion
sort, and almost every instance-optimal sorting algorithm, are equivalent in
cost to offline BST algorithms. Our main theoretical tool is the geometric
interpretation of the BST model introduced by Demaine et al. [19], which finds
an equivalence between searches on a BST and point sets in the plane
satisfying a certain property. To give an example of the utility of our
approach, we introduce the log-interleave bound, a measure of the information-
theoretic complexity of a permutation $\pi$, which is within a $\lg\lg n$
multiplicative factor of a known lower bound in the BST model; we also devise
a parallel sorting algorithm with polylogarithmic span that sorts a
permutation $\pi$ using comparisons proportional to its log-interleave bound.
Our aforementioned result on sorting and offline BST algorithms can be used to
show existence of an offline BST algorithm whose cost is within a constant
factor of the log-interleave bound of any permutation $\pi$.

###### keywords:

binary search trees, sorting, dynamic optimality, parallelism

###### category:

##  1 Introduction

Comparison-based sorting and searching on a BST are among the most elementary,
important, and well-studied algorithmic topics in all of theoretical computer
science. It has long been observed that they are closely related: both enjoy
better performance on sequences that are information-theoretically simpler,
such as reversals of sorted lists, sequences with long runs of consecutive
keys, or sequences composed from simple shuffles of sorted lists. Indeed,
their respective searches for instance optimality have yielded the independent
discovery of almost identical results [35]. Despite the extensive number of
similar results throughout the literature, there is comparatively very little
known about the formal relationship between sorting and the binary search tree
(BST) model. In this paper, we present what we believe to be the first formal
relation between the sorting cost model and the BST model. Our result shows
that a large class of sorting algorithms, which includes mergesort, quicksort,
insertion sort, and most adaptive sorting algorithms, are equivalent in cost
to offline algorithms in the BST model. As this class is large and contains
many well-studied algorithms, we find it interesting that we are able to show
any kind of new and nontrivial theoretical result based on this
characterization.

Binary Search Trees. The binary search tree is a fundamental data structure
that stores an ordered universe of keys in a dynamic tree. A search for a key
begins with a pointer to the root of the tree and at each step performs one of
two unit-cost actions: move the pointer to a parent or child node, or perform
a rotation. Rotations are key to understanding the power of the model, because
they allow frequently queried elements to be kept close to the root of the
tree as well as exploiting other kinds of order in the sequence of queried
keys. The power of rotations is related to the concept of instance optimality,
a general term which refers to the fact that an algorithm can enjoy
improvements on its worst-case complexity on well-defined sets of “easy”
inputs. Many BST algorithms perform better than their worst-case complexity
(i.e. $\log n$ per operation) on various kinds of input [38, 20, 19, 4].
Beyond these specific improvements, the hope for a more general kind of
instance optimality is crisply expressed by the dynamic optimality conjecture
of Sleator and Tarjan [36], which states that there exists a binary search
tree whose performance on any online sequence of searches is constant factor
competitive with the best offline algorithm for that sequence. The dynamic
optimality conjecture remains open. Another equally important open question is
whether there is an offline efficient algorithm for calculating even an
approximately optimal number of rotations for a given input sequence. These
problems have been the subject of extensive work both in the past [39, 17, 16,
20, 22, 9] and at the present moment [27, 14, 8, 26, 24].

Sorting. Similarly to the BST model, where rotations are used to achieve
instance optimality for particular classes of inputs, in comparison-based
sorting an adaptive sorting algorithm performs fewer comparisons when the
input is “closer” to sorted by some measure. In this field a measure of
disorder for a list $L$ is paired with an algorithm which is optimal for this
measure. Here, optimal roughly means that sorting $L$ only requires the number
of comparisons needed to distinguish it from all other lists which are more
presorted than $L$ [35]. An accompanying notion is that a measure of disorder
may be superior (inferior) to another measure—that is, always requires fewer
comparisons for any given permutation. Mannila first formalized these ideas
[32]. After this, many researchers devised new measures of disorder and
corresponding optimal algorithms [18, 23, 25, 29, 30, 28, 34, 35];
furthermore, there was also interest in work-optimal parallel versions of
optimal sorting algorithms [12, 31, 15]. It remains an open problem whether
there exists a measure which is provably superior to any possible measure of
disorder.

Arborally Satisfied Point Sets and Sorting. One of our most important tools in
connecting BSTs and sorting is the geometric interpretation of BSTs [19, 21].
In this interpretation, an access sequence of $n$ keys is represented as an
$n\times n$ grid with time order (input order) on one axis (here the $x$ axis)
and key order (output order) on the other axis. Points are added to the grid
to account for all keys that must be visited when searching or inserting the
keys one at a time from left to right. Demaine et al. [19], and Derryberry,
Sleator, and Wang [21] show that for any BST algorithm, the accesses plotted
in the plane must satisfy the property that for every pair of points $p,q$
(both original and added points), there is a monotonic path (e.g. up and
right) from $p$ to $q$ consisting of horizontal and vertical segments with a
point at each corner111The papers have their own preferred definition, but the
definitions are all equivalent.. Demaine et al. refer to such a set of points
as being _arborally satisfied_ , and show that any such set of size $m$
implies the sequence of $n$ keys can be searched or inserted in cost $O(m)$ in
the BST model.

We observe that the geometric approach is also useful for sorting, since
unlike the BST model, it does not directly enforce an order of insertion. As
some evidence of the utility of the geometric approach, consider the following
two algorithms that can be used to arborally satisfy a set of accesses. The
first algorithm starts by choosing a random point, then adding accesses to
that point across its entire row of the point set. Then, it recurses above and
below the row, and in each partition it picks a random point and adds new
points to all locations in its row for which there is a key in the partition.
It is not hard to verify the points added in this way are arborally satisfied:
any point $p$ can get to a point $q$ by going up (or down) to the row that
separated them, then across to column of $q$ and up (down) to $q$. Second,
consider another algorithm that adds points across the middle column, and then
for the left and right, add points along their middle columns for all points
in those halves. Recursing to the base case again gives an arborally satisfied
set. See Figure 1 for an example of both of these algorithms. The attentive
reader may have noticed that the accesses added in the first algorithm
correspond to the comparisons made by the quicksort algorithm, and the
accesses added in the second algorithm correspond to comparisons made by the
mergesort algorithm. We will extend these ideas to more interesting algorithms
in this paper.

(a) The input sequence

(b) Sequence arborally satisfied using quicksort

(c) Sequence arborally satisfied using mergesort

Figure 1: On the left, the input sequence plotted in the plane. In the middle,
the input sequence arborally satisfied using accesses corresponding to
quicksort. On the right, the input sequence arborally satisfied using accesses
corresponding to mergesort.

We note that in addition to being of significant theoretical interest, taking
advantage of locality in key sequences is widely practical for both search
trees and sorting. Sleator and Tarjan won the ACM Kannelakis Theory and
Practice award for their work on splay trees and its applications for reducing
key search time in several widely used applications. Adaptive sorting
algorithms are widely adopted in practice, including timsort, which is
implemented as built-in libraries for Python, Java, Swift, and Rust, among
other languages [3].

###  1.1 Our Results.

In this paper we present specific results relating sorting and BSTs using
arborally satisfied sets. Our first result is an explicit relation between the
cost models of a broad set of sorting algorithms and BST algorithms. The
specific set of algorithms, which we refer to as tree-based sorting algorithms
and which are formally defined in Section 3, are divided into two classes: BST
mergesorts are sorting algorithms based on recursive merges of the input,
where the keys being merged are stored in binary search trees; BT partition
sorts are sorting algorithms based on recursive partitions of the input based
on key ordering, where the keys are stored in a binary tree. In Section 3, we
show that these two types of algorithms are “dual” to each other in the
following way: a BST mergesort $\mathcal{A}$ sorting permutation $\pi$ with
cost $\mathcal{A}(\pi)$ implies the existence of binary tree (BT) partition
sort $\mathcal{B}$ sorting $\pi^{-1}$ with cost $\mathcal{A}(\pi)$, and vice
versa.

The category of tree-based sorting algorithms is large. Both quicksort and
mergesort on lists fall into the category of tree-based sorting algorithms, as
lists are simply a special case of trees. Sorting by insertion into a BST is
also a BST mergesort, since the merges can be carried out in any order.
McIlroy’s adaptive sorting algorithms—namely, insertion sort with exponential
search and mergesort with exponential search—are BST mergesorts [33]. These
algorithms were influential in the development of timsort [3], a mergesort
algorithm that breaks the input into runs of increasing or decreasing keys and
merges them based on certain ordering criteria; since it is also a mergesort
on lists, timsort is a BST merge. In their capstone paper on adaptive sorting,
Petersson and Moffat cover the three most powerful known adaptive sorting
algorithms—local insertion sort, historical insertion sort, and regional
insertion sort. Local insertion sort is a BST mergesort as it inserts into a
BST with a single additional pointer, which can be converted to the BST model
with constant overhead [14]. Historical and regional insertion sort are not
BST mergesorts as presented by the authors, but independently discovered data
structures would yield BST mergesorts with the same bounds [36, 22].

Theorem 1.1 shows that for any tree-based sorting algorithm that sorts access
sequence $\pi$ using $\mathcal{A}(\pi)$ accesses, there exists an offline
algorithm in the BST model which searches for each key in $\pi$ using
$O(\mathcal{A}(\pi))$ accesses. The proof of Theorem 1.1 is subtle and
nontrivial and requires several new insights relating to the geometric
interpretation of the BST model. In the following statement,
$\text{OPT}_{\text{BST}}(\pi)$ refers to the cost of the best offline
algorithm.

######  Theorem 1.1.

Let $\mathcal{A}$ be a tree-based sorting algorithm which sorts permutation
$\pi$ using $\mathcal{A}(\pi)$ accesses. Then $\text{OPT}_{\text{BST}}(\pi)\in
O(\mathcal{A}(\pi))$.

As some evidence for the utility of our approach, we introduce the log-
interleave bound, a measure of the information-theoretic complexity of a
permutation $\pi$. The log-interleave bound is an upper bound on the number of
bits needed to encode $\pi$; it can also be understood from an algorithmic
perspective as a mergesort with a more efficient merge step. Our main results
on the log-interleave bound illustrate the connections between sorting and the
BST model. In the statements of the following results, we use the notation
$\text{LIB}(\pi)$ to refer to the log-interleave bound of a permutation $\pi$.
This will be defined formally in Section 4.

The first result is a proof that the log-interleave bound is within a $\lg\lg
n$ multiplicative factor of the optimal offline BST algorithm on any
permutation. Somewhat similarly to Demaine et al.’s proof of the closeness to
optimality of tango trees [20], our proof shows closeness to optimality by
comparing the log-interleave bound with Wilber’s interleave bound [39], a
lower bound in the BST model.

theoremthmlib For any permutation $\pi$, $\text{IB}(\pi)\leq\text{LIB}(\pi)\in
O(\lg\lg n\;\text{IB}(\pi))$.

Next, we show that there is a work optimal parallel sorting algorithm related
to the log-interleave bound. The next result is a parallel mergesort featuring
a merge step which combines recent work on parallel split and join of BSTs [5]
with a BST from [10] and an analysis which shows that with this new merge
step, the mergesort sorts a sequence $\pi$ in $O(\text{LIB}(\pi))$ work. While
the span of this algorithm is greater than the span of a typical parallel sort
and indeed may be open to improvement, all existing parallel sorting
algorithms present guarantees only for very weak measures of disorder [15,
31].

theoremthmsort There exists a parallel mergesort which for any permutation
$\pi$ performs $O(\text{LIB}(\pi))$ work with polylogarithmic span.

Finally, a corollary of Theorem 3.3 shows that there is an offline BST
algorithm that incurs cost $O(\text{LIB}(\pi))$, and thus that the log-
interleave bound is an upper bound in the BST model.

corollarycorlib There exists an offline BST algorithm $\mathcal{A}$ such that
$\mathcal{A}(\pi)=O(\text{LIB}(\pi))$.

Model of Computation. Our results for the parallel algorithms are given for
the binary-fork-join model [6]. In this model a process can fork two child
processes, which work in parallel and when both complete, the parent process
continues. Costs are measured in terms of the work (total number of
instructions across all processes) and span (longest dependence path among
processes). Any algorithm in the binary forking model with $W$ work and $S$
span can be implemented on a CRCW PRAM with $P$ processors in $O(W/P+S)$ time
with high probability [2, 7], so the results here are also valid on the PRAM,
maintaining work efficiency.

###  1.2 Related Work.

Upper and Lower Bounds in the BST Model. The pursuit of dynamic optimality led
to a string of work in both upper and lower bounds on the cost of a sequence
of searches on a BST. Three important upper bounds in the literature are the
dynamic finger bound [36, 17, 16, 14, 9, 24], the working set bound [36], and
the unified bound [4, 22], which respectively state that accessing an element
is fast if its key is close to the key of the previous search, if its key has
been searched recently, and a combination of the two. There has also been
significant work in lower bounding the cost of an access sequence in the BST
model. Two such lower bounds, the interleave bound and the funnel bound, were
introduced by Wilber in [39]; a recent work by Lecomte and Weinstein [27]
affirmatively settled the 30-year open question of whether the funnel bound
was tighter than the interleave bound, proving a $\lg\lg n$ multiplicative
separation in some cases. Another lower bound, the rectangle bound, was
introduced by Demaine et al. in [19].

Progress on Dynamic Optimality. The BST which comes closest to dynamic
optimality is the tango tree of Demaine et al. [20], which has a competitive
ratio of $O(\lg\lg n)$ with respect to the best offline algorithm. Wilber’s
interleave bound was vital in the analysis of the competitive ratio, since the
authors showed that on any access sequence $x$, the tango tree uses $O(\lg\lg
n\;\text{IB}(x))$ accesses, where $\text{IB}(x)$ represents the interleave
bound of the sequence. In [38], Wang et al. introduce the multi-splay tree, a
BST which achieves $O(\lg\lg n)$ optimality with better worst-case guarantees
than the tango tree. Prominent candidates for a dynamically optimal algorithm
include the splay tree, which was presented by Sleator and Tarjan at the same
time as the dynamic optimality conjecture [36], and the Greedy algorithm
presented in Demaine et al.’s geometric interpretation of the BST model [19].

Other Data Structures and the BST model. The min-heap, which stores a set of
keys and supports inserting arbitrary elements and extracting and deleting the
minimum element. Recently, Kozma and Saranurak show an explicit relation
between the BST model and the heap cost model [26], as well as proposing an
analogue of the dynamic optimality conjecture for heaps. Specifically, they
show that for every heapsort algorithm (that is, an algorithm which sorts a
permutation $\pi$ with cost $\mathcal{A}(\pi)$ by inserting its keys into a
heap and repeatedly extracting the minimum element) corresponds to an
insertion sort into a BST algorithm which incurs cost $\mathcal{A}(\pi)$ on
the inverse permutation $\pi^{-1}$. Their insight came from relating the
rotation operation in a BST to the link operation in a heap, which allowed
them to relate the corresponding cost models.

Adaptive Sorting in Parallel. During the period of interest in the adaptive
sorting model, researchers were also interested in work-optimal parallel
sorting algorithms with polylogarithmic span. Unsurprisingly, such algorithms
exist for practical measures Runs and Inv [12, 15]; one also exists for Osc, a
generalization of Inv [31] that is still theoretically weak. To our knowledge
there are no results on parallel sorting algorithms which are optimal with
respect to any stronger measures.

##  2 Preliminaries

Terminology. Throughout this paper, we will use the terms list, permutation,
and access sequence interchangeably to refer to some ordering of the keys
$1,2,\ldots,n$. The term access sequence is used in the literature on BSTs to
denote a sequence of queries to a BST; unless otherwise stated, an access
sequence is presumed not to contain repeated keys.

The Binary Search Tree Model. A binary tree (BT) is either a _leaf_ or a
_node_ consisting of a left binary tree, a key and a right binary tree. A
binary seach tree (BST) is a binary tree where the keys have a total order,
and for each node in the tree all keys in its left subtree are less than its
key, and all keys in its right tree are greater.

The following definition of the BST model is drawn from [36, 39, 20]. The
model assumes an initial BST with keys $[1,2,\ldots,n]$ and an access sequence
$[x_{1},x_{2},\ldots,x_{m}]$ of searches, where $x_{i}\in\\{1,2,\ldots,n\\}$.
Each search starts at the root and at each node it visits, it may perform one
of the following actions: (a) move to the right child, left child, or parent,
or (b) perform a rotation of the node and its parent. Each of these actions
has unit cost and the search must visit its specified key. We refer to an
algorithm that decides on what actions to perform for each search as a BST
algorithm. A BST algorithm may be offline—meaning it can see the entire
sequence of queries ahead of time—or online, meaning that queries are revealed
one at a time.

Wilber’s Interleave Bound. Wilber’s interleave bound is a lower bound on the
cost of accessing any sequence in the BST model. Given an access sequence
$\pi$ consisting of the keys $x_{1},x_{2},\ldots,x_{n}$, fix a static binary
tree $P$ (meaning it will never be rotated) with the keys of $\pi$ at the
leaves in the order they appear in $\pi$. Calculate the interleave bound of
$\pi$ as follows: query the keys in $\pi$ in sorted order. For each vertex
$v_{j}$, label each element $i$ of the sequence with R or L, depending on
whether accessing $i$ in $P$ goes through the right or the left subtree of
$v_{j}$, respectively (if $i$ is in neither subtree, give it no label). The
interleave bound of $v_{j}$, denoted $\text{IB}(v_{j})$, is the number of
switches between $R$ and $L$ in the labels if the keys are queried in sorted
order. The interleave bound of the entire access sequence $\pi$ is calculated
by summing over the interleave bounds of each vertex, so
$\text{IB}(\pi)=\sum_{v\in P}\text{IB}(v_{i})$. As the lower bound holds for
an arbitrary tree $P$, the interleave bound of the sequence is usually
understood to refer to the maximum over all static trees. See Figure 3 for an
example calculation.

Arborally Satisfied Sets. In [22], Derryberry et al. formalize a connection
between binary search trees and points in the plane satisfying a certain
property. An access sequence can be plotted in the plane where one axis
represents key values and the other axis represents the ordering of the search
sequence (that is, time). In the context of sorting, these axes can also be
referred to as input order and output order. In this work, we use the
horizontal axis for time and the vertical access for keyspace. See Figure 1
for an example of an arborally satisfied set.

In addition to plotting the search sequence on the plane, one can also plot
the key values of the nodes which a BST algorithm accesses (for search or
rotations) while searching for a node. When searching for an element $x_{i}$
which is inserted at time $i$, the values of the nodes in the search path are
plotted on the same vertical. Demaine et al. [19] proved that such a plot
satisfies the following property:

######  Definition 2.1.

Given a set $P$ of points in the plane, $P$ is arborally satisfied if for
every two points $x,y\in P$ that are not on the same vertical or horizontal,
the rectangle defined by $x$ and $y$ contains at least one point in addition
to $x$ and $y$.

As mentioned in Section 1, a useful equivalent definition of arboral
satisfaction is that there must be a monotonic path (e.g. consisting only of
moves up and to the right) between $x$ and $y$ with a point at every corner.
Note that any valid search on a BST will only touch nodes in a subtree
$\tau_{i}$ of tree $T$, where $\tau_{i}$ includes the root of $T$. We
sometimes refer to such a subtree as a top tree of $T$.

Demaine et al. show that a BST can be used to arborally satisfy an access
sequence plotted in the plane. However, one can also use an algorithm that
directly places points in the plane rather than using a BST.

######  Definition 2.2.

Given a set of points in the plane corresponding to an access sequence $\pi$,
an offline arboral satisfaction algorithm adds points to the plane to make an
arborally satisfied set. An online arboral satisfaction algorithm also adds
points in the plane to form an arborally satisfied set, but accesses are
revealed one by one in input order and the algorithm must produce an arborally
satisfied set at each time.

Demaine et al. show that a BST algorithm is equivalent to an arboral
satisfaction algorithm, but they also show a more surprising result: an
arboral satisfaction algorithm is equivalent to a BST algorithm. Specifically,
they show that an offline (online) arboral satisfaction algorithm requiring
$f(\pi)$ accesses to arborally satisfy a search sequence $\pi$ can be
transformed to an offline (online) BST algorithm requiring $O(f(\pi))$
accesses to search for the elements of a sequence $\pi$.

##  3 Tree-based Sorting

Towards the goal of unifying the BST model and sorting, we ask the following
question: when can the costs of a sorting algorithm be related to the costs of
a BST algorithm? Clearly not every comparison-based sorting algorithm should
be relatable to the BST model: as mentioned in Section 1, for example, an
algorithm that guesses and checks could take $O(n)$ steps for an arbitrary
permutation. Our investigation is therefore limited to sorting over binary
trees, and in particular it considers a class of mergesort and partition sort
(related to quicksort) algorithms on binary trees.

###  3.1 Mergesort.

We first consider mergesorts in which the sequences to be merged are
represented as BSTs. “Mergesort” is interpreted here as merging based on any
split of the input sequence, not just splits into equally-sized parts; thus
insertion sort using a sequence of insertions into a BST is a special case of
mergesort. The cost of these algorithms is measured in terms of the number of
accesses to the tree required during the mergesort, which will always be at
least as great as the number of comparisons. We capture the idea of a BST
mergesort more formally before giving the theorem statement.

A merge will interleave contiguous subsequences from its two inputs. We refer
to each of these subsequences as _blocks_ and we refer to the ends of each
block as _block boundaries_. The block boundaries need to be accessed to even
verify that the merge is correct. The following defines a merge that examines
some top part of two trees to generate its output.

######  Definition 3.1.

A BST merge takes two BSTs $T_{A}$ and $T_{B}$, and for some top trees
$\tau_{a}$ of $T_{A}$ and $\tau_{b}$ of $T_{B}$, returns a BST $T$ such that
for some top tree $\tau$ of $T$, $\tau=\tau_{a}\cup\tau_{b}$, the subtrees of
$\tau$ correspond to unchanged subtrees of $\tau_{a}$ and $\tau_{b}$, and
$\tau$ contains the block boundaries. The _number of accesses_ used by the
merge is $|\tau|$.

######  Definition 3.2.

A BST mergesort recursively splits the input sequence into two parts each of
size at least 1, sorts each part with a BST mergesort, and executes a BST
merge on the results. A mergesort on an input of size 1 returns its input. The
_number of accesses_ used by the mergesort is the sum of accesses across all
merges.

This leads to the main theorem.

######  Theorem 3.3.

Let $\mathcal{A}$ be a BST mergesort algorithm which sorts permutation $\pi$
using $\mathcal{A}(\pi)$ accesses. Then $\text{OPT}_{\text{BST}}(\pi)\in
O(\mathcal{A}(\pi))$.

Theorem 3.3 is proved by showing that for every BST mergesort algorithm, there
is an offline BST algorithm that incurs the same cost as the BST mergesort
within a constant factor. Our proof relies on the geometric interpretation of
the BST model—instead of directly transforming a BST mergesort into an offline
BST algorithm we use arborally satisfied sets as an intermediary. The key
ingredient is a transformation of a BST merge algorithm to an offline
arborally satisfied set algorithm, which is equivalent to an offline BST
algorithm by Demaine et al.’s theorem [19]. The following graphic illustrates
the chain of dependencies.

Input: Two arborally satisfied sets $A,B$; BST merge algorithm $\mathcal{M}$.

Output: An arborally satisfied set $C$ consisting of the concatenation of $A$
and $B$ as well as additional accesses needed to arborally satisfy the
concatenation.

3 if  _$A==\emptyset$_ then return _$B$_ ;

4 if  _$B==\emptyset$_ then return _$A$_ ;

5 $C$ $\leftarrow$ concatenate $A$ and $B$ on the time axis ;

6 $S$ $\leftarrow$ set of keys accessed when merging keys in $A$ and $B$ using
$\mathcal{M}$ ;

7 access each key in $S$ in the first, middle (rightmost column of $A$), and
end columns of $C$ ;

8 return _$C$_ ;

The arboral satisfaction algorithm; also illustrated in Figure 2(a).

Algorithm 1 arboralMerge($A,B,\mathcal{M}$)

The arboral satisfaction algorithm; also illustrated in Figure 2(a).

The main idea behind going from the mergesort to an arborally satisfied set is
to transform a merge algorithm $\mathcal{M}$ into an algorithm that “merges”
two arborally satisfied sets by concatenating them along the time axis (in
this paper the $x$ axis) and resolving any unsatisfied rectangles between the
two sets, thus producing an arborally satisfied set. This “arboral” mergesort
algorithm would by definition be an offline arborally satisfied set algorithm.
Ideally this arboral merge would use the same number of accesses as a
corresponding BST merge $\mathcal{M}$. The key idea behind our algorithm is to
use the keys accessed during the tree merge to arborally satisfy the sets on
the two sides, as well as add points to make it easier to satisfy the
condition on future merges. In particular, the keys are added in three
columns: the leftmost column of the left set, the rightmost column of the
right set, and a middle column—we will use the rightmost of the left set,
although the leftmost of the right set would also work. Roughly, the accesses
are placed down the middle to resolve unsatisfied rectangles, and they are
placed down the leftmost and rightmost columns to restore invariants that are
useful for future merges. These accesses must by definition form top trees of
the two trees being merged. Algorithm 1 shows the merging routine, which is
used as a sub-step in an arborally satisfied set algorithm which recursively
splits the input set to singletons and then uses Algorithm 1 to merge sub-
parts of the input; see Figure 2(a) for an illustration of the merge step.
Since we are adding a constant number of points per access in the mergesort,
the total points added is proportional to the cost of the mergesort, which in
turn implies an offline BST algorithm with the same cost as the original BST
mergesort.

The most difficult part of Theorem 3.3 is proving correctness of the arboral
mergesort—that is, that each execution of the arboral merge routine produces
an arborally satisfied set. This will require some more background on
arborally satisfied sets.

(a) An illustration of an arboral merge

(b) A BST separated into a top tree and auxiliary trees

Figure 2: On the right, an illustration of the merging algorithm shown in
Algorithm 1. The blue squares represent members of the two sets being merged,
while the red columns (referred to as $C_{L},C_{M},C_{R}$ in the proof of
Theorem 3.3) illustrate the additional accesses necessary for the merge. A
path drawn from $a\in A$ to $b\in B$ illustrates how the accesses in the
middle column ensure the set is arborally satisfied. On the right, a BST with
a top tree shown in blue and auxiliary trees $T_{1}$ through $T_{6}$, where
the recursive structure is shown in $T_{1}$.

######  Definition 3.4.

A treap over a set of pairs $S$ is a BST over the first coordinate of each
$s\in S$ and a min-heap over the second coordinate. Ties over the second
coordinate are permitted and may be broken arbitrarily.

A treap with ties on the priorities can also be expressed as a multi-treap
(for multi-node treap), where ties are stored in a multi-node that may have
more than two children. Child relations must obey an underlying BST structure
on the nodes stored within a multi-node; hence a multi-node may have at most
one more child than the number of keys in the multi-node. A key component of
our proof is that we will define a multi-treap with respect to each side of an
arborally satisfied set and then relate these to the BST the mergesort will
generate.

######  Definition 3.5.

Given an arborally satisfied set $A$, let the left (right) priority be the
distance from the left (right) boundary of the first point in the row (closer
has higher priority). The _left (right) multi-treap_ of $A$ is the multi-treap
defined by the (row, priority) pairs.

Since there can be many points in any given column of an arborally satisfied
set, multi-nodes of the multi-treaps can have more than two
children.222Demaine et al. [19] define a similar notion when proving that for
any arborally satisfied set there is a BST execution with equivalent cost, but
only with respect to one side, and only when sweeping column by column.

######  Definition 3.6.

Given a BST $T$ and an arborally satisfied set $A$ with left (right) multi-
treap $H_{A}$, $T$ is _left (right) congruent with $A$_ if there is some valid
BST structure on $H_{A}$ (forming a binary subtree within each multi-node)
such that the tree structure on $H_{A}$ is equal to $T$. $T$ is _doubly_
congruent with $A$ if it is both left and right congruent.

Note that many BSTs can be left (equivalently right) congruent with the same
arborally satisfied set $A$ due to equal priorities. Also many arborally
satisfied sets can be left (right) congruent with the same BST $T$. It may
seem unlikely that a BST is doubly congruent with a arborally satisfied set,
but in our construction we will maintain double congruence, and in particular
we will show that the point sets created by Algorithm 1 are doubly congruent
to the corresponding tree.

The following observation will be useful for the proof of Theorem 3.3. It
follows from a similar argument to Lemma 2.1 of Demaine et al. [19].

Consider an arborally satisfied set $A$ that is double-congruent with a tree
$T$. Then for any top tree $\tau$ of $T$, if the keys in $\tau$ are accessed
along either the left or right column of $A$, or one past the left or right
column, the resulting set of points is arborally satisfied.

######  Proof 3.7.

Begin with the case where the keys of $\tau$ are accessed one past the
leftmost or rightmost column of $A$. Assume for the sake of contradiction that
there exists an unsatisfied rectangle—that is, a rectangle with two points at
its corners and no points contained within it—between access $a\in A$ and
access $b\in\tau$. Consider the least common ancestor $c$ of $a$ and $b$,
whose key value must be between those of $a$ and $b$. Since by our assumption,
there are no keys accessed between the rectangle defined by $a$ and $b$, this
contradicts the fact that $\tau$ is a continuous subtree of $T$, since $c$
must be accessed in $\tau$ to reach $b$.

This leaves the case where accesses to $\tau$ are instead placed on the
leftmost or rightmost column of $A$—that is, in addition to accesses that were
already there. Consider an arbitrary access $a\in A$ and any access
$b\in\tau$. If the accesses in $\tau$ are placed on a new column past the
rightmost (leftmost) column of $A$, there is a monotonic path from $a$ to $b$
with accesses at every corner. If the accesses in $\tau$ are imposed on the
rightmost (leftmost) column of $A$ instead, the same accesses still form a
monotonic path, since this only causes the elimination of one right (left)
move.

We now prove correctness of the arboral mergesort algorithm.

######  Lemma 3.8.

The arboral mergesort algorithm is correct: that is, it returns an arborally
satisfied set.

######  Proof 3.9.

We will use the following inductive hypothesis on the arboral merge algorithm
(Algorithm 1) to show correctness: Algorithm 1 returns an arborally satisfied
set which is double-congruent to the tree $T$ returned by the corresponding
BST mergesort algorithm.

Base Case. When the set is just a single point, both arboral satisfaction and
double congruence follow trivially.

Inductive Step. The inductive step is broken into several claims, and some new
notation is called for. The two arborally satisfied sets being merged are $A$
and $B$, and by the inductive hypothesis are both arborally satisfied and
double-congruent to trees $T_{A}$ and $T_{B}$, respectively. The additional
accesses specified by the mergesort are added to three columns. Let $C_{L}$,
$C_{R}$, and $C_{M}$ denote the set of points which the arboral merge adds
along the left, right, and middle columns respectively; see Figure 2(a) for an
illustration. It will also be useful to denote the subset of a $C_{i}$
($i\in\\{L,R,M\\}$) consisting only of accesses to keys in $A$ or $B$. These
subsets are denoted by $C_{i}(A)$ or $C_{i}(B)$.

The merge will break $A$ and $B$ into contiguous blocks that are interleaved
in key order. As assumed in the model, the block boundaries must be accessed
by the merge, and therefore included in the $C_{i}$. In general the $C_{i}$
will include other points as well. The inductive step has to show both that
the resulting set is arborally satisfied and is doubly congruent to the merged
tree $T$.

Arboral Satisfaction. Points within $A$ or $B$ are satisfied by the inductive
hypothesis. Points both in $C_{L},C_{R},C_{M}$ are satisfied by the fact that
they access precisely the same keys. This leaves the two more interesting
cases: (1) pairs of points one from the previously exiting points (in $A$ or
$B$) and one from the new boundaries $C_{L},C_{R},C_{M}$, and (2) pairs of
points one from $A$ and one for $B$. For the first case, $A$ is double-
congruent to tree $T_{A}$ (by the inductive hypothesis), and $C_{i}(A)$ is a
top tree of $A$ (by construction), so we can apply Observation 3.1 for points
in $A$ and $C_{i}(A)$. Now since the boundaries of each block of $A$ must be
in $C_{i}(A)$, we can get from a point in $A$ to a point in $C_{i}(B)$ using a
monotonic path by going to a boundary point in $C_{i}(A)$ and then up or down
the column to the point in $C_{i}(B)$. Symmetrically points in $B$ can get to
points in $C_{i}(B)$ and $C_{i}(A)$ by a monotonic path. For case (2) consider
any point $a\in A$ and point $b\in B$. There is a monotonic path between $a$
and $b$ by composing the monotonic path between $a$ and a boundary point in
$p_{a}$ in $C_{m}(A)$, between $b$ and a boundary point $p_{b}$ in $C_{m}(B)$,
and between $p_{a}$ and $p_{b}$, which are in the same column; see Figure
2(a).

Double congruency to $T$. We will show that the set $AB$ returned by the
arboral merge algorithm is right congruent to $T$. Left congruency is true by
symmetry. The keys in $C_{R}$ (those accessed by the merge) correspond to a
top tree $\tau$ of $T$. Since all keys in the column $C_{R}$ have the same
highest priority we can organize the root multi-node to match the structure of
$\tau$ making those nodes congruent. Now consider the subtrees not in $\tau$.
They properly are lower in the tree and have equal or lower priority (only
equal if they happen to be in the last row). Furthermore the subtrees are
separated by keys in $\tau$. Each such subtree either comes completely from
$T_{A}$ or completely from $T_{B}$ and have the same structure as before the
merge (they were not touched by the merge). Furthermore the points from
$T_{A}$ ($T_{B}$) only appear in $A$ ($B$). This implies the relative
priorities have not change for those points when merging into $AB$. By
induction, the trees $T_{A}$ ($T_{B}$) were congruent to $A$ ($B$) before the
merge so the subtrees were congruent and remain congruent after the merge
(neither the relative priorities nor tree structure have changed). This
implies the whole tree $T$ is congruent with $AB$.

The proof of Theorem 3.3 now follows easily.

######  Proof 3.10 (Proof of Theorem 3.3).

The theorem follows once the cost of the arboral mergesort is shown to be
$O(\mathcal{A}(\pi))$. Since the cost of $\mathcal{A}$ is dominated by the
cost of each merge execution, and that cost is at most multiplied by six in
each call to the arboral merge, the cost of the arboral mergesort is at most
$6\mathcal{A}(\pi)$. When the arboral mergesort is transformed into an offline
BST algorithm, the cost remains the same for a total cost of
$O(\mathcal{A}(\pi))$.

###  3.2 Partition Sort

We now consider a class of sorting algorithms motivated by quicksort, which we
refer to as partition sorts. As in the case of mergesort, we limit ourselves
to working with binary trees. However, in this case the trees are not ordered
by key, but instead are ordered by input order. The algorithm is like
quicksort in that it picks a pivot, partitions the keys on the pivot and
recurses. Since we are interested in lower bounds (i.e. showing the cost of
partition sort is at least as great as optimal BSTs), we can assume an oracle
picks the perfect pivot (e.g., the median). As with mergesort, to achieve
better than trivial $O(n\log n)$ bounds it is important that the partition
need not visit the whole tree it is partitioning, but rather just some top
tree. This allows for sending whole subsequences to the lesser or
greater/equal side without visiting all nodes. More precisely here are the
definitions of partition and partition sort.

######  Definition 3.11.

A BT partition takes a BT $T$ and for some top tree $\tau$ of $T$ returns two
BTs $T_{A},T_{B}$ with distinct keys such that for some top trees $\tau_{a}$
of $T_{A}$ and $\tau_{b}$ of $T_{B}$, $\tau=\tau_{a}\cup\tau_{b}$, the other
subtrees of $T$ appear in either $T_{A}$ or $T_{B}$ unchanged, and $\tau$
contains the block boundaries of the partitioned output. Furthermore the
preordering of the keys in $T_{A}$ or $T_{B}$ are a subsequence of the
preordering in $T$ (i.e. left-to-right ordering). We assume both partitions
are non-empty. The _number of accesses_ used by the partition is $|\tau|$.

######  Definition 3.12.

A BT partition sort on a BT tree $T$ (1) partitions $T$ into $T_{a}$ and
$T_{b}$ such that for some key $k$ all keys in $T_{a}$ are less than $k$ and
all keys in $T_{b}$ are greater or equal to $k$, (2) recurses on each
partition, and (3) returns the left and right results appended. The recursion
terminates when the tree is of size one. The number of accesses used by the
partition sort is the sum of accesses across all partitions.

Our goal is to show the following theorem, which has the same form as the
result for mergesort.

######  Theorem 3.13.

Let $\mathcal{A}$ be a BT partition sort algorithm that sorts permutation
$\pi$ using $\mathcal{A}(\pi)$ accesses, and let
$\text{OPT}_{\text{BST}}(\pi)$ be the optimal cost of querying $\pi$ with a
BST algorithm. Then $\text{OPT}_{\text{BST}}(\pi)\in O(\mathcal{A}(\pi))$.

Our approach is to show a one-to-one correspondence between the tree-based
merge and partition sorts.

######  Lemma 3.14.

For any BT partition sort algorithm $\mathcal{A}$ that sorts permutation $\pi$
using $\mathcal{A}(\pi)$ accesses, there is a BST mergesort sort algorithm
$\mathcal{B}$ that sorts permutation $\pi^{-1}$ using
$\mathcal{B}(\pi^{-1})=\mathcal{A}(\pi)$ accesses, and vice versa.

######  Proof 3.15.

The idea is to consider running BST mergesort backwards, while reversing the
role of time and key order. Consider undoing a merge—i.e. taking the merged
tree and partitioning back into its two inputs. Reversing the roles of time
and keys, this is equivalent to a BT partition where keys are time order and
the partitions is on the first time of the right partition. In particular the
size of the top tree and therefore access cost is identical. This continues to
be true on the recursive calls. In both cases the base case is of size one.
Hence the total access costs of the two algorithms are identical, one applied
to the inverse permutation of the other.

Since the size of arborally satisfied sets are invariant under rotation by 90
degrees, reversing the role does not affect the size of the set. Since the
proof of Theorem 3.3 first showed how to map a BST mergesort to an arborally
satisfied set and this implied the same bound on a offline BST, this remains
true if we rotate the input, arborally satisfy it in the same way, and
generate a BST. Theorem 3.13 follows. Taken together, Theorem 3.3 and Theorem
3.13 show the statement in Theorem 1.1. Although the duality of mergesort and
quicksort has been recognized before we are not aware of any formal
correspondence such as the one given here.

##  4 The Log-Interleave Bound

The following two sections contain results that illustrate the utility of the
approach shown in Theorem 1.1: namely, that results in the sorting cost model
can directly translate to interesting results in the BST model. In this
section we propose an information-theoretic bound on both the cost of
accessing a sequence in the BST model and sorting a list in the comparison
model. Theorem 1.1 shows that the log-interleave bound is within a $\lg\lg n$
multiplicative factor of a known lower bound in the BST model. In the next
section, we show that there exists a BST mergesort algorithm that sorts any
permutation $\pi$ in $O(\text{LIB}(\pi))$ comparisons, and thus combined with
Theorem 3.3 shows the existence of an offline BST algorithm with the same
costs in the BST model.

The log-interleave bound can be thought of as an algorithmic perspective on
Wilber’s interleave bound. Let $P$ be the static tree with the keys of a
permutation $\pi$ at the bottom. Consider sorting $\pi$ via mergesort:
clearly, each non-leaf vertex of $P$ denotes a merge. The interleave bound
charges unit cost for each switch between the right and left subtree during a
merge. Another way of looking at this cost is that every continuous run of
accesses to the left subtree incurs unit cost. Thus, a mergesort with a merge
step that incurred unit cost for each consecutive run—as opposed to the
standard mergestep which charges for the size of each run—would sort $\pi$
using $O(\text{IB}(\pi))$ comparisons.

Lecomte and Weinstein [27] and Chalermsoook et al. [13] independently show
that the merge step described above does not exist. However, it is possible to
charge the logarithm of the size of each consecutive run, as shown by Brown
and Tarjan in [11]. This idea leads us to using such a merge step as an
information-theoretic bound, which applies to sorting (sequentially and in
parallel), and the BST model. The log-interleave bound is formally defined
below; note its similarity to the interleave bound.

Figure 3: Consider accessing the keys 1-8 in order. For the vertex $v_{1}$ at
the root of the tree shown here, the labeled access sequence is [L, L, L, R,
L, R, R, R]. Since the access sequence switches between the left and right
subtree three times, $\text{IB}(v_{1})=3$. Similarly, $\text{LIB}(v_{1})=\lg
4+\lg 2+\lg 2+\lg 4$ since the smallest possible decomposition of the labeled
access sequence consists of [[L, L, L], [R], [L], [R, R, R]].

######  Definition 4.1.

Given an access sequence $\pi$, fix a static binary tree $P$ with the keys of
$\pi$ at the leaves. For each vertex $v_{j}$, query the descendants of $v_{j}$
in sorted order, then label each with R or L depending on whether it is in the
left or right subtree of $v_{j}$. Let $S(v_{j})$ represent the decomposition
of this labeling into the smallest possible number of runs of consecutive
accesses to L or R in $v_{j}$. Then $\text{LIB}(v_{j})=\sum_{r_{i}\in
S(v_{j})}\lg(|r_{i}|+1)$ and $\text{LIB}(\pi)=\sum_{v\in P}\text{LIB}(v_{i})$.

See Figure 3 for an example calculation.

A natural question one might ask about a BST algorithm or an adaptive sorting
algorithm is how far, in the worst case, is the cost of this algorithm from
any known lower bounds? Or, in other words, how close is this algorithm to
optimal? In this section, we will settle this question for the log-interleave
bound in the BST model, ending in the following theorem:

Our first step is to show that we cannot hope to do better than a $\lg\lg n$
separation; this is stated in the following lemma. This result is similar to
the separation result in Theorem 2 of Lecomte and Weinstein [27]; furthermore,
the result implies that an online BST algorithm using $\text{LIB}(\pi)$
accesses cannot be dynamically optimal.

######  Lemma 4.2.

There exists a permutation $\pi$ such that $\text{LIB}(\pi)=\Theta(\lg\lg
n\;\text{IB}(\pi))$.

######  Proof 4.3.

First we will need to define a particularly useful permutation. The bit-
reversal permutation $\pi_{B}$ on $n=2^{k}$ keys is generated by taking a
sorted list $[0,1,\ldots,n]$, writing each key in binary, then reversing the
bits of each key. For example, the bit-reversal permutation on 8 keys is
$[0,4,2,6,1,5,3,7]$. Let $P$ be a static tree with keys of $\pi_{B}$ at the
bottom: then querying its keys in sorted order will switch between the left
and right subtree of any $v_{j}\in P$ on each query. This implies that
$\text{IB}(\pi_{B})=\Theta(n\lg n)$, thus showing that any BST algorithm will
incur this cost when querying $\pi_{B}$.

Consider the permutation $\pi$ obtained by splitting the sorted list into
$n/\lg n$ segments of equal size, and then permuting those $n/\lg n$ segments
according to the bit-reversal permutation $\pi_{B}$.

The interleave bound of $\pi$ will be the same as for a list with $n/\lg n$
elements permuted according to the bit-reversal sequence—that is, $(n/\lg
n)\lg(n/\lg n)=O(n)$. In $\pi$, every block is of size $\lg n$, so to
calculate the log-interleave bound, we multiply by $\lg\lg n$ on all but the
bottom $\lg\lg n$ levels. Thus, the log-interleave bound of $\pi$ is
$\Theta(n\lg\lg n)$ while $\text{IB}(\pi)=O(n)$.

Now we have shown there is no possibility of doing better than a $\lg\lg n$
separation, we show that this separation is tight. This starts with the
following question: when are the interleave bound and the log-interleave bound
farthest apart? It follows from the convexity of the logarithm that for each
vertex $v_{j}$ of a static tree, the interleave bound and the log-interleave
bound are farthest apart when $v_{j}$ experiences long runs of consecutive
accesses to its subtrees (e.g. the list [L, L, L, R, R, R] has fairly
different values for its interleave bound and log-interleave bound, but the
list [L, R, L, R, L, R] does not).

However, a completely sorted list $\pi_{S}$—translating to the longest run
size possible for each vertex of $P$—has
$\text{IB}(\pi_{S})=\text{LIB}(\pi_{S})=\Theta(n)$. This suggests there must
be some intermediate value of the block size that maximizes the difference
between the two bounds. As the reader might have inferred from Lemma 4.2, that
size will turn out to be $\lg n$. The next lemma, whose proof follows directly
from the convexity of the logarithm, formalizes this intuition.

######  Lemma 4.4.

For a permutation $\pi$, let $v$ be a vertex of the corresponding static tree
$P$ such that $\text{IB}(v)=S$. Then $\text{LIB}(v)$ will differ from
$\text{IB}(v)$ by the greatest amount when each “run” of L or R in the labeled
sequence is the same size.

Now that we have established that the interleave bound and the log-interleave
bound differ the most when all continuous runs are the same size, we move on
to ask the following question: how large do the runs of the same size have to
be to further maximize this difference? The next lemma shows this fact in the
following way: in the inequality below, the expression
$S\lg\left(\frac{n}{S}+1\right)$ bounds the log-interleave bound of any $\pi$
such that $\text{IB}(\pi)=S$. The left-hand expression $c\lg(\lg
n+1)\left(S+\frac{n}{\lg n}\right)$ will directly suffice to prove Theorem
1.1. The proof of the lemma draws out the fact that the two expressions are
closest to each other when the size of the continuous runs is $\lg n$.

######  Lemma 4.5.

For a permutation $\pi$, let $v$ be a vertex of the corresponding static tree
$P$ such that $\text{IB}(v)=S$. Furthermore, let the number of leaves below
vertex $v$ be $n$. Then for some constant $c$,

$\displaystyle c\lg(\lg n+1)\left(S+\frac{n}{\lg n}\right)\geq
S\lg\left(\frac{n}{S}+1\right).$

######  Proof 4.6.

Assume for the sake of contradiction that

$\displaystyle c\lg(\lg n+1)S+c\lg(\lg n+1)\frac{n}{\lg
n}<S\lg\left(\frac{n}{S}+1\right).$

This would imply that each added term is smaller than
$S\lg\left(\frac{n}{S}+1\right)$. Begin by examining the case where the first
term is smaller than the term on the right:

$\displaystyle\lg(\lg n+1)S<S\lg\left(\frac{n}{s}+1\right)$
$\displaystyle\implies\lg(\lg n+1)<\lg\left(\frac{n}{S}+1\right)$
$\displaystyle\implies\lg n<\frac{n}{S}$ $\displaystyle\implies S<\frac{n}{\lg
n}.$

This shows that when $S\geq\frac{n}{\lg n}$, we reach a contradiction and our
claim holds. Now, when $S<\frac{n}{\lg n}$, the second term in the sum
dominates. When the second term dominates, the expression reads

$\displaystyle c\lg(\lg n+1)\cdot\frac{n}{\lg n}\geq\frac{n}{\lg n}\lg(\lg
n+1)$

which is self-evidently true for all $c\geq 1$.

Now, these two lemmas are put together to prove Theorem 1.1.

######  Proof 4.7 (Proof of Theorem 1.1).

Let $P$ be the static tree corresponding to $\pi$, and for each vertex $v_{i}$
of $P$, let $S_{i}=\text{IB}(v_{i})$. By Lemma 4.4, we can assume that if the
number of leaves below $v_{i}$ is $n_{i}$, then
$\text{LIB}(v_{i})=S_{i}\lg\left(\frac{n_{i}}{S}+1\right)$. Then
$\text{IB}(\pi)=\sum_{i=1}^{n-1}S_{i}$. Next, we can use the upper bound on
$\text{LIB}(v_{i})$ from Lemma 4.5 to upper bound $\text{LIB}(\pi)$:

$\displaystyle\text{LIB}(\pi)\leq\sum_{i=1}^{n-1}c\lg\lg
n\left(S+\frac{n_{i}}{\lg n}\right)$ $\displaystyle=c\lg\lg
n\left(\text{IB}(\pi)+\frac{1}{\lg n}\sum_{i=1}^{\lg
n}2^{i}\frac{n}{2^{i}}\right)$ $\displaystyle=c\lg\lg
n\left(\text{IB}(\pi)+n\right)=O(\text{IB}(\pi)\lg\lg n).$

##  5 Adaptive Parallel Mergesort

In this section we present a parallel BST mergesort which sorts a permutation
$\pi$ using $O(\text{LIB}(\pi))$ accesses, and the same amount of work. We
refer to the algorithm as an adaptive parallel mergesort.

First we introduce a few basic terms and the data structure used in our
mergesort. Given a BST $T$ and a key $k$, a split refers to returning two
BSTs, one containing all keys from $T$ which are greater than $k$, and one
containing all keys which are less than $k$. Given two BSTs $T_{1},T_{2}$ such
that any key in $T_{1}$ is greater than every key in $T_{2}$, join returns a
single BST $T$ containing the union of the keys in $T_{1}$ and $T_{2}$. As
previously stated, we assume keys are unique.

The tree used in our mergesort algorithm is a modified red-black tree
described by Tarjan and Van Wyck in [37], which they call a heterogeneous
finger search tree. These trees have the useful property that a key $d$ in a
heterogenous finger search tree with $n$ elements can be accessed in time
$O(\log(\min(d,n-d)+1))$. This property allowed Tarjan and Van Wyck to devise
fast split and join algorithms for heterogenous finger search trees; split
runs in amortized time $O(\lg(\min(|T_{1}|,|T_{2}|)+1))$—that is, the
logarithm of the size of the smaller tree returned. Join similarly is bounded
by amortized time $O(\lg(\min(|T_{1}|,|T_{2}|)+1))$—in this case, the size of
the smaller of the two trees being joined together. The worst-case complexity
of split and join is $O(\log\max{|T_{1}|,|T_{2}|})$. As presented in [37], the
heterogeneous finger search tree is not strictly a BST as it uses more than
one pointer; however, work by [14] shows how it can be converted into using a
single pointer with an additional constant factor loss.

Sequential Mergesort. As a warmup, we present a sequential merge algorithm
which, when used in as the merge step of a mergesort algorithm, sorts a
permutation $\pi$ in $O(\text{LIB}(\pi))$ time. Refer to Algorithm 2 for the
algorithm. We note that McIlroy also proposed a sequential comparison-based
sorting algorithm that uses $O(\text{LIB}(\pi))$ comparisons [33], but his
algorithm uses a merge step which requires linear time in the size of the
lists being merged.

Input: Two BSTs $T_{1},T_{2}$ with disjoint keys.

Output: A BST containing the union of the keys of $T_{1}$ and $T_{2}$.

1 $T=\emptyset$ ;

2 while  _true_ do

3 if  _$T_{1}=$ leaf_ then return _join ( $T,T_{2}$)_ ;

4 else if  _$T_{2}=$ leaf_ then return _join ( $T,T_{1}$)_ ;

5 else

6 $k_{1}=\min(T_{1})$; $k_{2}=\min(T_{2})$;

7 if  _$k_{1} >k_{2}$_ then

8 $t,T_{2}=$ split($T_{2},k_{1}$) ; $T=$ join($T,t$);

9

10 else

11 $t,T_{1}=$ split($T_{1}$, $k_{2}$) ; $T=$ join($T,t$) ;

12

Algorithm 2 merge($T_{1},T_{2}$).

######  Lemma 5.1.

Algorithm 2 is correct and, if it breaks $T_{1}$ into subtrees
$t_{1},\ldots,t_{j}$ and $T_{2}$ into subtrees $t_{j+1},\ldots,t_{k}$, then it
runs in time

$\displaystyle O\left(\sum_{i=1}^{k}\lg(|t_{i}|+1)\right).$

######  Proof 5.2.

The proof of the time bound is immediate, since a heterogeneous finger search
tree has split and join cost $O(\lg(|t|+1))$ for every subtree that it breaks
off from $T_{1}$ and $T_{2}$.

Correctness will be shown via induction. The inductive hypothesis is that
after each split and join of a new subtree, $T$ remains a valid BST, and each
key of $T$ is smaller than every key in $T_{1}\cup T_{2}$.

The base case is when $T$ is empty. Assume without loss of generality that
$k_{1}>k_{2}$. Then $\text{split}(T_{2},k_{1})$ returns $T_{2}$ and $t$, where
$t$ contains only keys which are smaller than all keys in $T_{2}$. They are
also smaller than all keys in $T_{1}$, since $k_{1}$ was the minimum key in
$T_{1}$ and $t$ contains only keys less than $k_{1}$. The operation
$\text{join}(T,t)$ successfully returns the BST $t$ since $T=\emptyset$.

Now, assume that after any number of split/join actions that $T$ is a valid
BST and contains only keys that are less than those in $T_{1}\cup T_{2}$.
Similarly to the proof of the base case, assuming wlog that $k_{1}>k_{2}$, we
know that the split of $T_{2}$ returns a tree $t$ such that each key in $t$ is
larger than any key in $T$, and such that each key in $t$ is smaller than any
key in $T_{1}\cup T_{2}$. Furthermore, since $t$ contains only keys larger
than those in $T$, $\text{join}(T,t)$ returns a valid BST.

Next, we show that the mergesort algorithm which uses Algorithm 2 as its merge
routine is optimal for the log-interleave bound.

######  Lemma 5.3.

When Algorithm 2 is used as the merge step in a mergesort algorithm, the
mergesort will sort a sequence $\pi$ in time $O(\text{LIB}(\pi))$.

######  Proof 5.4.

When merging two trees $T_{1},T_{2}$, consider any permutation $\pi$ such that
the keys of $T_{1}$ correspond to the keys in the first half of $\pi$, and the
keys of $T_{2}$ correspond to the keys in the second half of $\pi$.

Consider the static tree $P_{\pi}$ used to calculate the log-interleave bound
of $\pi$. The root vertex $v$ then contains all the keys in $T_{1}$ in its
left subtree, and all the keys in $T_{2}$ in its right subtree. Thus

$\displaystyle\text{LIB}(v)=\sum_{i=1}^{k}\lg(|t_{i}|+1)$

since the $t_{i}$’s correspond to switching between $T_{1}$ and $T_{2}$ when
querying the keys in sorted order.

Finally, observe that each non-leaf vertex of $P_{\pi}$ corresponds to a merge
that a mergesort algorithm would carry out, and the result follows.

The natural parallel equivalent of the merge presented in Algorithm 2 is as
follows: starting with two trees, split each tree using the other tree’s root;
then, recurse in parallel to merge the two left halves and the two right
halves, respectively, joining the two at the end. This idea was presented by
Blelloch et al. [5], and is shown here in Algorithm 3. This algorithm,
however, does not meet the log-interleave bound even if we use heterogeneous
finger search trees for the split and join. We therefore modify the algorithm
as is shown in Algorithm 4 and illustrated in Figure 4, which follows the same
idea with some small modifications. In addition to splitting the second tree
$T_{2}$ into $L_{2}$ and $R_{2}$ based on the root of the first tree
($T_{1}$), it then splits $T_{1}$ by the maximum value of $L_{2}$ and the
minimum value of $R_{2}$ to effectively break $T_{1}$ into three parts. The
middle part need not be split recursively since it falls between two elements
of $T_{2}$. This avoids redundant splits.

Input: Two BSTs $T_{1},T_{2}$ with disjoint keys.

Output: A BST containing the union of the keys of $T_{1}$ and $T_{2}$

3 if  _$T_{1}=$ Leaf_ then return _$T_{2}$_ ;

4 else if  _$T_{2}=\text{Leaf}$_ then return _$T_{1}$_ ;

5 else

6 $L_{1},k_{2},R_{1}=$ expose($T_{1}$);

7 $L_{2},R_{2}=$ split($T_{2},k$) ;

8 do in parallel

9 $T_{L}=$ union($L_{1},L_{2}$);

10 $T_{R}=$ union($R_{1},R_{2}$) ;

11

12return _join( $T_{L},k_{2},T_{R}$)_;

Blelloch et al.’s union algorithm. Here, the function expose refers to
returning the root and its right and left subtrees.

Algorithm 3 union($T_{1},T_{2}$).

Blelloch et al.’s union algorithm. Here, the function expose refers to
returning the root and its right and left subtrees.

Input: Two BSTs $T_{1},T_{2}$

Output: A BST containing the union of the keys of $T_{1}$ and $T_{2}$

3 if  _$T_{1}=$ Leaf_ then return _$T_{2}$_ ;

4 else if  _$T_{2}=\text{Leaf}$_ then return _$T_{1}$_ ;

5 else

6 $k$ = root($T_{1}$);

7 $L_{2},R_{2}=$ split($T_{2},k$) ;

8 $k_{1}=$ max($L_{2}$) ; $k_{2}=$ min($R_{2}$) ;

9 $L_{1},I=$ split($T_{1},k_{1}$) ;

10 $M,R_{1}=$ split($I$, $k_{2}$) ;

11 do in parallel

12 $T_{L}=$ merge($L_{1},L_{2}$) ;

13 $T_{R}=$ merge($R_{1},R_{2}$) ;

14

15return _join(join( $T_{L},M$), $T_{R}$)_;

Pseudocode for the merge step of our mergesort.

Algorithm 4 mergeHT($T_{1},T_{2})$

Pseudocode for the merge step of our mergesort.

Unlike the sequential algorithm, it is not immediate that even our modified
algorithm’s work is bounded by the log-interleave bound, since it performs a
different set of splits and joins than the sequential version. We will show
that this different sequence of splits and joins also performs within the log-
interleave bound, culminating in the following theorem:

Figure 4: One round of our recursive merge algorithm. The nodes shown in red
are the nodes used to split a tree; the small blue nodes denote merges.

First, we introduce a useful lemma which shows that the work performed to
split a heterogeneous finger search tree into $k$ smaller trees is independent
of the order in which the splits are carried out.

######  Lemma 5.5.

Let $T$ be a heterogeneous finger search tree and consider splitting $T$ into
$k$ smaller trees $t_{1},\ldots,t_{k}$. Then the work required to split $T$ is
$O\left(\sum_{i=1}^{k}\lg(|t_{i}|+1)\right)$ regardless of the order in which
the splits are performed.

######  Proof 5.6.

The proof proceeds by induction on the size. Let $|T|=n$, and make an
inductive hypothesis that the total split work of $T$ is

$\displaystyle\left(\sum_{i=1}^{k}\lg(|t_{k}|+2)\right)-(\lg n+2).$

Begin by verifying the base case: splitting a BST of size 1 should have a cost
of zero:

$\displaystyle\lg(1)+2-(\lg(1)+2)=0.$

Now, for the inductive step, assume we are splitting $T$ into two parts of
size $\alpha n$ and $(1-\alpha)n$ for $\alpha\in[0,1]$, and that the first
part consists of the smaller trees $t_{1},\ldots,t_{j}$ while the second part
consists of the trees $t_{j+1},\ldots,t_{k}$. Then our inductive step requires
that:

$\displaystyle\left(\sum_{i=1}^{j}\lg|t_{i}|-\lg(\alpha
n)-2\right)+\left(\sum_{i=j+1}^{k}\lg|t_{i}|-\lg((1-\alpha))n-2\right)$
$\displaystyle+\lg(\min(\alpha
n,(1-\alpha)n))+1\leq\sum_{i=1}^{k}\lg|t_{i}|-\lg n-2$

Assume without loss of generality that the size of the first subtree is
smaller than the second, i.e. $\alpha\in[0,\frac{1}{2}]$. Then canceling on
both sides and substituting in the minimum value gives:

$\displaystyle-\lg(\alpha n)-\lg((1-\alpha)n)-4+\lg\alpha n+1\leq-\lg n-2$
$\displaystyle\lg((1-\alpha)n)+1\geq\lg n.$

Finally, since $1-\alpha\in[\frac{1}{2},1]$, in the case where the right-hand
expression is smallest and $\alpha=\frac{1}{2}$, $\lg(\frac{1}{2}n)+1=\lg n$,
so the inequality is both true and tight in the worst case.

This lemma allows us to show the correctness and the work bounds for Algorithm
4.

######  Lemma 5.7.

Algorithm 4 is correct, and if merging $T_{1}$ and $T_{2}$ requires $T_{1}$
and $T_{2}$ to be split into $k$ trees $t_{1},\ldots,t_{k}$ and $j$ smaller
trees $t_{1},\ldots,t_{j}$ respectively, then Algorithm 4 performs
$O(\sum_{i=1}^{k}\lg|t_{i}+1|+\sum_{i=1}^{j}\lg|t_{i}+1|)$ work.

######  Proof 5.8.

Correctness follows from the fact that by the assumptions on the input, the
interval $I$ contains all keys between those of $L_{1},L_{2}$ and
$R_{1},R_{2}$, and from the correctness of Algorithm 3.

The work bound comes from Lemma 5.5, which shows that it does not matter in
what order the splits are performed, and therefore they are bounded by the
sequential work. Since each join is the same cost as a split, the proof of
Lemma 5.5 also suffices to show that the join work is bounded by the split
work, so the work bound follows.

Note that the position of the “root” in the tree $T_{1}$ as selected in line 4
does not matter for the purpose of the work bounds. Picking the first element,
for example, would lead to an algorithm that is very similar to the sequential
algorithm. However for the purpose of parallelism it is important that the
root in near the middle—i.e., cuts off at least a constant fraction of
$T_{1}$’s keys from each side. This could be achieved by finding the median
element, and the cost would be within bounds.

Our last lemma concerns the span of the parallel mergesort algorithm.

######  Lemma 5.9.

The span of the parallel adaptive mergesort is $O(\lg^{3}n)$.

######  Proof 5.10.

Our merge has the same span as Blelloch et al.’s union algorithm since split
and join have the same worst-case guarantees; they proved in [5] that the span
of the merge is $O(\lg^{2}n)$ when merging two trees of size $n$. Since
parallel mergesort has span $O(\lg n)$, the total span is $O(\lg^{3}n)$. We
only require binary forking since the only parallel calls are the two
recursive calls inside merge, and the two recursive calls inside mergesort.

Now, we can put all these results together to prove our theorem.

######  Proof 5.11 (Proof of Theorem 1.1).

Lemma 5.5 shows that the merge step in our parallel mergesort performs the
same amount of work as the mergestep in the sequential mergesort from Lemma
5.3; Lemma 5.7 shows correctness. Lemma 5.9 shows the span.

A natural corollary of Theorem 1.1 and Theorem 3.3 now follows. Notably, this
corollary shows that the log-interleave bound is in fact an upper bound in the
BST model.

######  Proof 5.12 (Proof of Corollary 1.1).

Theorem 1.1 gives a BST mergesort that has the desired bounds; thus Theorem
3.3 implies the existence of an offline BST algorithm.

## References

  * [1] Peyman Afshani, Jérémy Barbay, and Timothy M. Chan.  Instance-optimal geometric algorithms.  J. ACM, 64(1):3:1–3:38.
  * [2] N. S. Arora, R. D. Blumofe, and C. G. Plaxton.  Thread scheduling for multiprogrammed multiprocessors.  Theory of Computing Systems (TOCS), 34(2), Apr 2001.
  * [3] Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau.  On the worst-case complexity of TimSort.  In European Symposium on Algorithms (ESA), volume 112. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [4] Mihai Badoiu, Richard Cole, Erik D. Demaine, and John Iacono.  A unified access bound on comparison-based dynamic dictionaries.  Theoretical Computer Science, 382(2), 2007.
  * [5] Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun.  Just join for parallel ordered sets.  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2016.
  * [6] Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun.  Optimal parallel algorithms in the binary-forking model.  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020.
  * [7] Robert D. Blumofe and Charles E. Leiserson.  Scheduling multithreaded computations by work stealing.  J. ACM, 46(5), 1999.
  * [8] Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, and Stefan Langerman.  Competitive online search trees on trees.  In ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2020\.
  * [9] Prosenjit Bose, Karim Douïeb, John Iacono, and Stefan Langerman.  The power and limitations of static binary search trees with lazy finger.  In International Symposium on Algorithms and Computation (ISAAC), volume 8889. Springer, 2014.
  * [10] Mark R Brown and Robert E Tarjan.  A fast merging algorithm.  Journal of the ACM (JACM), 26(2), 1979.
  * [11] Mark R. Brown and Robert Endre Tarjan.  Design and analysis of a data structure for representing sorted lists.  SIAM J. Comput., 9(3):594–614, 1980.
  * [12] Svante Carlsson and Jingsen Chen.  An optimal parallel adaptive sorting algorithm.  Inf. Process. Lett., 39(4), 1991.
  * [13] Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak.  Pinning down the strong wilber 1 bound for binary search trees.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, volume 176 of LIPIcs, pages 33:1–33:21. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.APPROX/RANDOM.2020.33.
  * [14] Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak.  Multi-finger binary search trees.  In International Symposium on Algorithms and Computation (ISAAC), volume 123. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [15] Jingsen Chen and Christos Levcopoulos.  Improved parallel sorting of presorted sequences.  In Joint Conference on Vector and Parallel Processing ( CONPAR \- VAPP), volume 634. Springer, 1992.
  * [16] Richard Cole.  On the dynamic finger conjecture for splay trees. Part II: The proof.  SIAM Journal on Computing, 30(1), 2000.
  * [17] Richard Cole, Bud Mishra, Jeanette Schmidt, and Alan Siegel.  On the dynamic finger conjecture for splay trees. Part I: Splay sorting log n-block sequences.  SIAM Journal on Computing, 30(1), 2000.
  * [18] Curtis R. Cook and Do Jin Kim.  Best sorting algorithms for nearly sorted lists.  Communications of the ACM, 23(11), 1980.
  * [19] Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Patrascu.  The geometry of binary search trees.  In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.
  * [20] Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu.  Dynamic optimality–almost.  SIAM Journal on Computing, 37(1), 2007.
  * [21] J. Derryberry, D. D. Sleator, and C. C. Wang.  A lowerbound framework for binary search trees with rotations.  Technical report, Technical Report CMU-CS-05-187, School of Computer Science, Carnegie Mellon University, 2005.
  * [22] Jonathan Derryberry.  Adaptive Binary Search Trees.  PhD thesis, Carnegie Mellon University, 2009.
  * [23] Vladimir Estivill-Castro and Derick Wood.  A new measure of presortedness.  Information and Computation, 83(1), 1989.
  * [24] John Iacono and Stefan Langerman.  Weighted dynamic finger in binary search trees.  In ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2016\.
  * [25] Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson.  Local insertion sort revisited.  In International Symposium on Optimal Algorithms, 1989.
  * [26] László Kozma and Thatchaphol Saranurak.  Smooth heaps and a dual view of self-adjusting data structures.  In ACM Symposium on Theory of Computing (STOC). ACM, 2018.
  * [27] Victor Lecomte and Omri Weinstein.  Settling the relationship between Wilber’s bounds for dynamic optimality.  In European Symposium on Algorithms (ESA), 2020.
  * [28] Christos Levcopoulos and Ola Petersson.  Adaptive heapsort.  Journal of Algorithms, 14(3), 1983.
  * [29] Christos Levcopoulos and Ola Petersson.  Sorting shuffled monotone sequences.  In Scandinavian Workshop on Algorithm Theory, 1990.
  * [30] Christos Levcopoulos and Ola Petersson.  Splitsort–an adaptive sorting algorithm.  Information Processing Letters, 39(4), 1991.
  * [31] Christos Levcopoulos and Ola Petersson.  Exploiting few inversions when sorting: Sequential and parallel algorithms.  Theor. Comput. Sci., 163(1&2), 1996.
  * [32] Heikki Mannila.  Measures of presortedness and optimal sorting algorithms.  IEEE Transactions on Computers, C-34(4), 1985.
  * [33] Peter McIlroy.  Optimistic sorting and information theoretic complexity.  In ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993.
  * [34] Alistair Moffat and Ola Petersson.  Historical searching and sorting.  In International Symposium on Algorithms, 1991.
  * [35] Ola Petersson and Alistair Moffat.  A framework for adaptive sorting.  Discrete Applied Mathematics, 59, 1995.
  * [36] Daniel Dominic Sleator and Robert Endre Tarjan.  Self-adjusting binary search trees.  J. ACM, 32(3), 1985.
  * [37] Robert Endre Tarjan and Christopher J. Van Wyk.  An $O(n\log\log n)$-time algorithm for triangulating a simple polygon.  SIAM J. on Computing, 17(1), 1988.
  * [38] Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator.  _O_(log log _n_)-competitive dynamic binary search trees.  In ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM Press, 2006.
  * [39] Robert Wilber.  Lower bounds for accessing binary search trees with rotations.  SIAM Journal on Computing, 18(1), 1989.