Introduction
Maintaining ordered data under online updates is a fundamental algorithmic task. Consider an array of size n n n that must store a sequence of elements drawn from a fixed range, say [ 0 , 1 ] [0,1] [ 0 , 1 ] . Elements arrive online, one at a time, and upon arrival must be assigned positions in the array. How should we arrange these elements so as to preserve as much order as possible while performing as little rearrangement as possible?
This question is elegantly captured in the online sorting problem, recently introduced by [2 ] , and further studied by [ABB⁺24, NW26, APV26a, Hu26, KPT26, Her26, PT26, FK26, BBI⁺26, AAB⁺27]. Here, the objective is to insert the elements in the array with the goal of minimizing the sum of absolute differences between consecutive elements in the array. Recent work has developed a rich theory of online sorting, establishing upper and lower bounds on the value of the objective that can be maintained without element rearrangement. The central result is that for element insertions, a competitive ratio of O ( n ) O(\sqrt{n}) O ( n ) can be achieved [2 ] , and this is tight [2 ABB⁺24] . But, what if we have both element insertions and deletions , i.e., we are in the fully dynamic setting? In this case, it is easy to establish a lower bound of Ω ( n ) \Omega(n) Ω ( n ) , which matches the trivial upper bound of O ( n ) O(n) O ( n ) where the elements are re-sorted after each insertion/deletion. So, we ask:
Using limited recourse, can we achieve non-trivial bounds on the competitive ratio of the fully-dynamic sorting problem? Furthermore, using limited recourse, can we also improve on the O ( n ) O(\sqrt{n}) O ( n ) bound for online (i.e., insertion-only) sorting?
Our Results
Fully-dynamic Sorting. First, we consider the more general problem of fully-dynamic sorting. Our main result is a deterministic algorithm with a O ( polylog ( n ) ) O(\operatorname{polylog}(n)) O ( polylog ( n )) -competitive ratio, while incurring O ( polylog ( n ) ) O(\operatorname{polylog}(n)) O ( polylog ( n )) amortized recourse.
Theorem 1. There is a deterministic algorithm for the fully dynamic sorting problem that maintains an array of size n n n under arbitrary insertions and deletions, with competitive ratio O ( log 2 n ) O(\log^{2} n) O ( log 2 n ) and O ( log 4 n ) O(\log^{4} n) O ( log 4 n ) amortized recourse per update.
We complement this upper bound with a lower bound showing that any deterministic algorithm with an O ( polylog ( n ) ) O(\operatorname{polylog}(n)) O ( polylog ( n )) competitive ratio for this problem must incur Ω ( log n ) \Omega(\sqrt{\log n}) Ω ( log n ) amortized recourse. So, our upper bound is tight up to the exact exponents in the poly-logs.
Theorem 2. Let 1 ≤ C ≤ O ( n ) 1 \le C \le O(n) 1 ≤ C ≤ O ( n ) . Any deterministic C C C -competitive algorithm for fully dynamic sorting with amortized recourse ρ \rho ρ satisfies
ρ = Ω ( log n log C + log n ) . \rho= \Omega\left(\frac{\log n}{\log C+\sqrt{\log n}}\right). ρ = Ω ( log C + log n log n ) .
Insertion-only Sorting. Next, we consider the online (i.e., insertion-only) sorting problem. We show that in this case, we can obtain an exponential improvement over the lower bound in Theorem 2 by giving a deterministic O ( log log n ) O(\log\log n) O ( log log n ) -approximation using O ( log log n ) O(\log\log n) O ( log log n ) amortized recourse.
Theorem 3. There is a deterministic algorithm for the online sorting problem with competitive ratio O ( log log n ) O(\log\log n) O ( log log n ) and O ( log log n ) O(\log\log n) O ( log log n ) amortized recourse per insertion.
More generally, we obtain a family of tradeoffs between approximation and amortized recourse in the insertion-only setting, which we present in § 7 . In addition to Theorem 3 , this tradeoff also yields approximations of O ( log n ) O(\log n) O ( log n ) and O ( 1 ) O(1) O ( 1 ) with O ( 1 ) O(1) O ( 1 ) and O ( log n ) O(\log n) O ( log n ) amortized recourse respectively. These approximation bounds are at least exponentially better than the lower bound of Ω ( n ) \Omega(\sqrt{n}) Ω ( n ) that can be obtained without recourse.
Finally, a popular line of work within online sorting explores the problem when the array has extra space. The works of [2 NW26, 4 ] have shown that with an array of size ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n , one can achieve exponential improvements on the competitive ratio of online sorting. We show that this phenomenon is also true for fully-dynamic sorting. Namely, we give a black-box reduction showing that in an array of size ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n , fully-dynamic sorting reduces to online (i.e., insertion only) sorting with O ( 1 ) O(1) O ( 1 ) overhead in cost and additive O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) overhead in recourse.
Theorem 4. Suppose the array has size ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n for any fixed ε > 0 \varepsilon> 0 ε > 0 . Then every deterministic online sorting algorithm with competitive ratio c c c and amortized recourse r r r can be transformed into a deterministic fully dynamic sorting algorithm with competitive ratio 2 c + 1 2c+1 2 c + 1 and amortized recourse r + O ( 1 / ε ) r+O(1/\varepsilon) r + O ( 1/ ε ) per update.
In particular, Theorems 3 and 4 imply that with ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n space, fully dynamic sorting admits an O ( log log n ) O(\log\log n) O ( log log n ) competitive ratio with O ( log log n + 1 / ε ) O(\log\log n+1/\varepsilon) O ( log log n + 1/ ε ) amortized recourse.
Our Techniques
Fully-Dynamic Upper Bound (Theorem 1 ). The high-level idea in fully-dynamic sorting is to move any holes created by element deletions to the end of the array, while keeping the array approximately sorted. Then, insertions can happen only at the end of the array, with local re-sorting and periodic merger of the newly inserted elements into the rest of the array.
To implement the operation of moving a hole efficiently through the array, we recursively organize the array into a data structure that we call a Dynamic Sorting Tree (DST). The challenge is to avoid shifting all intervening elements while ensuring that successive deletions don’t accumulate too much disorder. The DST organizes the array recursively at geometrically decreasing size scales, where a level-i i i DST comprises blocks that are themselves composed of sections, each of which is a level-( i − 1 ) (i-1) ( i − 1 ) DST. The sections are labeled either as original or transfer sections, the intuition being the original sections are the ones created when the DST is initialized in sorted order, while the transfer sections allow limited disorder and are created in the process of moving holes through the DST.
Crucially, a transfer section is allowed to contain elements larger than those in the original section that follows it. When a hole reaches the beginning of the original section, we first switch it to the transfer section by changing their shared boundary. No element moves, but the hole is now at the end of the transfer section. We fill this hole with a carefully chosen minimum element from an original section further to the right and in a lower recursive level. The ordering constraints ensure that this element is larger than the receiving transfer section’s existing elements, and so, accepting it requires no shift of its contents. The resulting hole is now in the original section that lost an element, but since we have moved one level down in the recursion, this process can be continued down the recursion tree.
In addition to these moves, we also need to initially move the hole from the position of the deleted element (which can be arbitrary) to the beginning of an original section. This requires further recursive moves within the section containing the deleted element, which are morally similar to moving the hole across the DST albeit at a lower recursive level. Combining these two recursively defined operations, the one that initially moves the hole to the beginning to an original section, and the other that moves it all the way to the end of the array, yields a recourse bound of O ( i 3 ) O(i^3) O ( i 3 ) for an i i i -level DST. Moving elements and changing section boundaries gradually alters section sizes, which is fixed by periodic calls to a rebuilding operation that reconstitutes a DST that violates its size invariants. Rebuilding is expensive, but it only done occasionally, thereby allowing us to amortize the resulting recourse to a sequence of element deletions preceding it. Finally, the approximation bound is controlled by ordering invariants that we maintain between the different sections in the DST. For a level-i i i DST, this yields a cost bound of O ( i ) O(i) O ( i ) times the overall range of values stored in the DST.
To support insertions as well as deletions, we arrange independent DST components of decreasing depths into an Augmented Dynamic Sorting Tree (A-DST), with no ordering constraints between components. A deletion first routes its hole to the end of its component and then through the subsequent components to the small terminal component, where new elements are inserted. Periodic suffix rebuilding consolidates a suffix into a clean DST and empties its smaller components, maintaining the geometric size bounds. Each such reconstruction is amortized over a number of updates proportional to the suffix’s size bound, contributing only O ( d ) O(d) O ( d ) amortized recourse for a d d d -level structure. The component cost bounds sum to O ( d 2 ) O(d^2) O ( d 2 ) , while hole routing together with structural rebuilding incurs O ( d 4 ) O(d^4) O ( d 4 ) amortized recourse per update. Choosing d = Θ ( log n ) d = \Theta(\log n) d = Θ ( log n ) therefore gives an O ( log 2 n ) O(\log^2 n) O ( log 2 n ) competitive ratio with O ( log 4 n ) O(\log^4 n) O ( log 4 n ) amortized recourse.
Fully-Dynamic Lower Bound (Theorem 2). Fix a deterministic C C C -competitive algorithm. We show that maintaining sorting cost at most C ⋅ O P T C \cdot\mathrm{OPT} C ⋅ OPT requires large recourse. The adversary works in rounds. Each round starts with the array containing n n n equally spaced valued in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and has two phases. During the forward phase , the adversary repeatedly deletes an existing element and inserts a copy of 1. At some stage, the adversary switches to the backward phase , where it removes the 1s it had inserted and restores the original elements. This marks the start of the next round. Since all values lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , we always have O P T ≤ 1 \mathrm{OPT} \le1 OPT ≤ 1 , so the algorithm must maintain sorting cost at most C C C .
The challenge is to choose the deletions so that the algorithm must either move many elements or incur a large cost. The adversary organizes the original values into a hierarchy of intervals. For each interval I v I_v I v , some child intervals are labeled targets , that can be further explored for reaching a leaf for deletion, and others buffers , that cannot. The labels are chosen using the algorithm’s current arrangement. The adversary divides the elements of the middle children intervals, in array order, into consecutive groups called windows . It chooses the labels for the children so that a constant fraction of these windows are balanced , meaning that each contains many elements of both types.
If the algorithm moves enough buffer elements, we call the corresponding interval I v I_v I v paid . These movements contribute to the recourse lower bound, and so the adversary releases its buffer children and allows their elements to be further explored towards a leaf. This lets the adversary continue removing original elements, rather than stopping at buffers for which the algorithm has already incurred the required recourse. The forward phase ends once the adversary cannot remove any additional element using legal search moves.
To bound the cost, we define, for any interval I v I_v I v , the cost through the interval as the sum of lengths of intersects between I v I_v I v and the interval spanned by each pair of consecutive array elements. The importance of this parameter is that the total cost of the array is lower bounded by the sum of costs through any set of disjoint intervals. Our main lemma states that for unpaid intervals I v I_v I v , either many original elements in I v I_v I v that belonged to target children were not changed to 1, or the cost through I v I_v I v is large compared to the length of I v I_v I v . We now use the main lemma recursively to conclude that at most n / 4 n/4 n /4 original elements remain at the end of the forward phase using an appropriate choice of parameters. This implies that there are many paid intervals. An interval that never becomes paid retains at least half of its original elements. Since few original elements remain, the paid intervals at each depth must together have held Ω ( n ) \Omega(n) Ω ( n ) elements at the start of the round. Using the definition of a paid interval, this implies that the algorithm must have moved Ω ( n ) \Omega(n) Ω ( n ) original buffer elements in total at each depth. We show that these movements can be chosen so that none is counted at two different depths. Summing over the d d d depths gives Ω ( n d ) \Omega(nd) Ω ( n d ) recourse in a round of O ( n ) O(n) O ( n ) updates, and hence Ω ( d ) \Omega(d) Ω ( d ) amortized recourse. Choosing the branching factor and depth appropriately then yields the stated tradeoff with cost C C C .
Online (Insertion-Only) Sorting (Theorem 3). Our insertion-only algorithm proceeds in two stages. First, we partition the insertion sequence into geometrically decreasing batches and use the recent online sorting algorithm of [4 ] to transform each batch into a contiguous sorted block while incurring only O ( 1 ) O(1) O ( 1 ) amortized recourse per element and constant cost. This reduces the problem to maintaining a sequence of sorted blocks in an approximately sorted array. The remaining challenge is to balance two competing objectives: keeping few sorted regions, which leads to a low competitive ratio, and minimizing the number of times each block is re-sorted, which leads to low recourse.
To resolve this tension, we introduce two complementary block gadgets. The Low Recourse Block Gadget organizes the blocks as the leaves of a virtual b b b -ary tree and re-sorts the blocks corresponding to completed subtrees. Since every block belongs to only one subtree at each height, it participates in just O ( log b k ) O(\log_b k) O ( log b k ) re-sorts, giving O ( log b k ) O(\log_b k) O ( log b k ) amortized recourse, at the cost of maintaining up to O ( b ) O(b) O ( b ) active subtrees per level and hence a competitive ratio of O ( b log b k ) O(b\log_b k) O ( b log b k ) . The High Recourse Block Gadget instead maintains a hierarchy of sorted super-blocks of geometrically increasing capacities, merging a super-block into its parent whenever it becomes full. This ensures that there is only one sorted super-block per level, yielding a competitive ratio of O ( log b k ) O(\log_b k) O ( log b k ) , but each block may be merged O ( b ) O(b) O ( b ) times per level, resulting in O ( b log b k ) O(b\log_b k) O ( b log b k ) amortized recourse. By choosing the branching factor b b b , the two gadgets yield complementary approximation–recourse tradeoffs, including O ( log n ) O(\log n) O ( log n ) approximation with O ( 1 ) O(1) O ( 1 ) recourse and O ( 1 ) O(1) O ( 1 ) approximation with O ( log n ) O(\log n) O ( log n ) recourse.
Fully-Dynamic Sorting with ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -Space (Theorem 4). For an array with ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n space, we reduce fully dynamic sorting to online sorting, establishing their equivalence in this setting. The reduction periodically rebuilds the array, leaving an empty buffer of size ε n \varepsilon n ε n ; insertions are handled online, while deletions are deferred until the next rebuild. Rebuilding every ε n \varepsilon n ε n updates adds only O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) amortized recourse. We note that, at a high level, our periodic rebuilding strategy is similar in spirit to the reduction from fully-dynamic to online list labeling with extra space in [10 ] , although the technical details of the two reductions are different.
Related Work
Online Sorting. The online sorting problem was introduced by Aamand et al. [2 ] , who established tight deterministic bounds of Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) for m = n m=n m = n , later extended to randomized algorithms by Abrahamsen et al. [3 ] . For m = ( 1 + ε ) n m=(1+\varepsilon)n m = ( 1 + ε ) n , Aamand et al. [2 ] established a deterministic lower bound of Ω ( log n / log log n ) \Omega(\log n/\log\log n) Ω ( log n / log log n ) and a subpolynomial upper bound. Subsequent works [NW26, APV26a] obtained polylogarithmic upper bounds, with Azar et al. [4 ] achieving O ( log 2 n / ε ) O(\log^2 n/\varepsilon) O ( log 2 n / ε ) competitiveness and O ( 1 ) O(1) O ( 1 ) competitiveness with O ( n log 2 n ) O(n\log^2 n) O ( n log 2 n ) space when the value range is known. Azar et al. [5 ] extended these results to online metric TSP, which was introduced by [3 ] , obtaining an O ( log 3 n / ε ) O(\log^3 n/\varepsilon) O ( log 3 n / ε ) -competitive algorithm using m = ( 1 + ε ) n m=(1+\varepsilon)n m = ( 1 + ε ) n space. They also showed that when opt is unknown, any deterministic algorithm using m = n 1 + δ m = n^{1+\delta} m = n 1 + δ space has competitive ratio Ω ( 1 / δ ) \Omega(1/\delta) Ω ( 1/ δ ) , even for online sorting.
Several variants of online sorting have also been studied. Under stochastic and random-order arrivals, recent works established tight logarithmic bounds [3 , 30 , 33 , 29 , 38 , 22 ] . Bercea et al. [6 ] also studied the problem in the learning-augmented setting, establishing tight consistency robustness tradeoffs. Finally, online sorting techniques have been applied to geometric problems, initially for lower bounds [2 ] . While recently in [1 ] several upper bounds for geometric problems are shown, the major one being an O ( log 2 n ) O(\log^2 n) O ( log 2 n ) -competitive algorithm for online translational packing of convex polygons.
Recourse in Online and Fully-Dynamic Algorithms. Allowing online algorithms to revise earlier decisions while bounding the number of such changes, known as recourse , has proved powerful across a wide range of problems. This includes matching, scheduling, load balancing, and network flows [27 KLS23] , Steiner tree and forest [24 , 35 ] , and minimum spanning tree and TSP [36 ] . These works demonstrate that even limited recourse can substantially improve the achievable competitive ratio compared with irrevocable online algorithms.
A closely related line of research studies recourse in the fully-dynamic setting, where elements or requests may both arrive and depart. Bounded-recourse algorithms have been developed for load balancing [21 , 17 ] , Steiner tree [25 ] , graph spanners [18 ] , set cover and submodular cover [26 , 28 , 39 , 40 , 14 ] , facility location and clustering [19 , 34 , 23 , 13 BCF25a, BCF+25b] , and bin packing [20 ] . More general frameworks for controlling recourse in dynamic settings have also been developed [7 ] .
Online List-Labeling. The online list labeling (also known as file maintenance ) problem introduced by [31 ] asks a complementary question for the same setting of element insertions: what is the minimum recourse of an algorithm that is required to keep the array precisely sorted? For deterministic algorithms, tight bounds of Θ ( log 2 n ) \Theta(\log^2 n) Θ ( log 2 n ) and Θ ( log n ) \Theta(\log n) Θ ( log n ) amortized recourse are known for linear and polynomial space, respectively [16 ] . Recent randomized algorithms have improved the linear-space upper bound to O ( log n ⋅ polyloglog n ) O(\log n \cdot\operatorname{polyloglog} n) O ( log n ⋅ polyloglog n ) [12 , 11 , 10 ] . Our work can be interpreted as relaxing the requirement that the array stays perfectly sorted, while allowing bounded recourse.
Organization of the Paper
We begin in Section 3 by giving a simple 2-level data structure that presents some of our ideas in fully-dynamic sorting without the technical complications of the full result. We then introduce the Dynamic Sorting Tree (DST) in Section 4 and build on it to construct the Augmented Dynamic Sorting Tree (A-DST) in Section 5; the A-DST structure realizes Theorem 1. In Section 6, we establish our lower bound for this setting. Section 7 considers the insertion-only setting (online sorting), where we design two new data structures, the Low Recourse Block Gadget and the High Recourse Block Gadget, and use them to yield Theorem 3. Finally, in Section 8, we extend these tradeoffs to the fully dynamic setting with ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n space, establishing Theorem 4. All proofs that are omitted from the main body of the paper appear in the appendix.
Preliminaries
We consider an array of size m ≥ n m \ge n m ≥ n storing real-valued elements that arrive online, where n n n is an upper bound on the number of elements present at any time. Each element occupies a distinct cell, so the array has at least m − n m-n m − n empty cells.
Let S = ( x 1 , … , x k ) S=(x_1,\ldots,x_k) S = ( x 1 , … , x k ) denote the elements currently stored in the array, ordered from left to right and ignoring empty cells. The cost of the array is
cost ( S ) = ∑ j = 1 k − 1 ∣ x j + 1 − x j ∣ . \operatorname{cost}(S)=\sum_{j=1}^{k-1}\lvert x_{j+1}-x_j\rvert. cost ( S ) = j = 1 ∑ k − 1 ∣ x j + 1 − x j ∣ .
An optimal offline arrangement sorts the elements and therefore has cost OPT ( S ) = max S − min S \operatorname{OPT}(S)=\max S-\min S OPT ( S ) = max S − min S . For sequences containing at most one element, both costs are defined to be zero.
It will be useful to express the cost in terms of threshold crossings. For a threshold z ∈ R z\in\mathbb{R} z ∈ R , let cross z ( S ) \operatorname{cross}_z(S) cross z ( S ) denote the number of adjacent pairs in S S S with one element at most z z z and the other greater than z z z . Formally,
cross z ( S ) = ∣ { j ∈ [ k − 1 ] : ( x j > z ) ≠ ( x j + 1 > z ) } ∣ . \operatorname{cross}_z(S)=\left\lvert\left\{j\in[k-1]:(x_j>z)\ne(x_{j+1}>z)\right\}\right\rvert. cross z ( S ) = ∣ { j ∈ [ k − 1 ] : ( x j > z ) = ( x j + 1 > z ) } ∣ .
For sequences containing at most one element, this number is zero. Since each adjacent pair crosses precisely the thresholds between its two values, summing over all pairs gives
cost ( S ) = ∫ R cross z ( S ) d z . (1) \operatorname{cost}(S)=\int_{\mathbb{R}}\operatorname{cross}_z(S)\,dz. \tag*{(1)} cost ( S ) = ∫ R cross z ( S ) d z . (1)
The recourse of an update is the number of previously stored elements that change positions during that update. We measure amortized recourse as the total recourse over a sequence of updates divided by the number of updates.
Insertion-Only and Fully Dynamic Updates. We consider two variants of online sorting. In the insertion-only setting, elements arrive one at a time and remain in the array permanently. Upon each arrival, the algorithm must assign the new element to an empty cell, possibly rearranging previously inserted elements.
In the fully dynamic setting, the algorithm must also support deletions of previously inserted elements. A deletion frees the cell occupied by the removed element, and the algorithm may rearrange the remaining elements to maintain a low-cost array. We assume that at most n n n elements are present at any time.
Initialization and Reduction to Deletion-Insertion Pairs. We describe our fully dynamic algorithm under the simplifying assumption that updates consist of deletion-insertion pairs. To handle arbitrary update sequences, we initialize an A-DST containing n n n virtual elements, all with value 0 0 0 and marked as inactive. These elements are initially sorted, and the A-DST is constructed with all transfer sections empty. Since no active elements are present, this initialization incurs no recourse.
When an active element is deleted, we simply mark it as inactive without changing the array. When a new element x x x arrives, we choose an arbitrary inactive element y y y , delete it from the A-DST, and insert x x x using a deletion-insertion pair. Such an inactive element always exists, since immediately before an insertion there are at most n − 1 n-1 n − 1 active elements. Thus, the A-DST maintains exactly n n n elements throughout the execution, some of which may be inactive. Inactive elements correspond to empty cells in the actual array, but their values are retained internally for comparisons.
The active elements, in their relative order, form a subsequence of the sequence maintained by the A-DST. By the following lemma, a bound on the number of crossings at every threshold for the maintained sequence also holds for the active elements, preserving the competitive guarantee. Moreover, each actual insertion requires only one deletion-insertion pair, while actual deletions incur no recourse. Consequently, the amortized recourse bound for deletion-insertion pairs also applies to arbitrary update sequences.
Lemma 5. Let S ′ S' S ′ be a subsequence of a sequence S S S . Then, for every threshold z z z , cross z ( S ′ ) ≤ cross z ( S ) \operatorname{cross}_z(S') \le\operatorname{cross}_z(S) cross z ( S ′ ) ≤ cross z ( S ) . In particular, if cross z ( S ) ≤ C \operatorname{cross}_z(S) \le C cross z ( S ) ≤ C for every z z z , then cost ( S ′ ) ≤ C ⋅ OPT ( S ′ ) \operatorname{cost}(S') \le C \cdot\operatorname{OPT}(S') cost ( S ′ ) ≤ C ⋅ OPT ( S ′ ) .
Thus, an algorithm that guarantees at most C C C crossings at every threshold remains C C C -competitive when inactive elements are ignored. For algorithms satisfying this crossing bound, it therefore suffices to analyze deletion–insertion pairs.
Intuition: A 2-Level Data Structure
We first describe a 2-level data structure that captures some of the intuition of our eventual data structures, DST and A-DST, while keeping the technical details much simpler. We then give the actual construction of our data structures in the next two sections, and establish Theorem 1.
By the previous section, we imagine, w.l.o.g., that we start with a sorted array and then handle an alternating sequence of element deletions and insertions. Deleting an element from a sorted array creates a hole. A naïve idea is to move this hole to the end while preserving sorted order, then insert the next element in this hole, and move this element by shifting elements to its position in the sorted order. While this keeps the array precisely sorted, it incurs Θ ( n ) \Theta(n) Θ ( n ) recourse in each step. (Throughout this section, n n n denotes the size of the array.) Instead, we allow a limited amount of disorder within the array, so that a hole can pass through the array more efficiently.
To illustrate the idea, consider partitioning the array into approximately n \sqrt{n} n blocks, each containing approximately n \sqrt{n} n elements. We keep the blocks ordered by value, i.e., for two consecutive blocks, all elements in the right block are larger than all elements in the left block. Initially, we also sort the elements within each block.
Now, suppose there is a hole inside a block. With O ( n ) O(\sqrt{n}) O ( n ) element movements, we can move the hole to the end of the block. Filling the hole with the minimum element of the next block, the hole moves to the beginning of the next block. But, how do we now move the hole to the end of the next block? Doing this naïvely would incur O ( n ) O(\sqrt{n}) O ( n ) movement in the next block as well, which would create Θ ( n ) \Theta(n) Θ ( n ) movement overall across the O ( n ) O(\sqrt{n}) O ( n ) blocks.
To make this more efficient, we divide each block into a transfer section T T T followed by an original section O O O . (Initially, T T T is empty and the block only has O O O .) Each section is individually sorted, but every element of T T T is larger than every element of O O O . In other words, the two sections are opposite to the sorted order. (For example, see the third block in the final row of Figure 1 .) This means that the minimum element of a block is at the beginning of O O O , which is adjacent to the maximum element of the block, which is at the end of T T T . This adjacency is crucial. Suppose the hole is at the end of T T T in a block. We fill this hole with the minimum element of the next block, which is at the beginning of its original section. Since the hole now lies immediately after the transfer section of the next block, we can assign this empty cell to T T T by changing the boundary between the two sections. This boundary change moves no elements. This shifts the hole to the end of the transfer section of the next block, thereby recreating our starting configuration in the next block.
Figure 1. Deletion of 4 in the simplified two-level structure. After deleting 4, the hole is moved to the end of O 2 O_2 O 2 . The subsequent transfers move 8 into O 2 O_2 O 2 , 9 into T 2 T_2 T 2 , and 13 into T 3 T_3 T 3 . The last two transitions are shown separately: first borrowing 13 from B 4 B_4 B 4 , then shifting 14 to leave the hole in the final cell. Gray and blue cells belong to original and transfer sections; the red outline marks the hole. Dotted arrows indicate element movements.
Cascading these steps across the O ( n ) O(\sqrt{n}) O ( n ) blocks, we can move a hole at the end of the transfer section in any block to the end of the transfer section in a later block, with recourse proportional to the total number of blocks. This efficient method of moving a hole through the array, while only creating limited disorder, lies at the heart of our construction.
Finally, to complete the picture, we need to describe the initial steps that brings the hole to the end of T T T in a block, and the final movement that brings it to the end of the last block. For the two-level data structure, this can be done by simply shifting elements in the block originally containing the hole and in the last block, incurring O ( n ) O(\sqrt{n}) O ( n ) moves in each step. However, to introduce the structure used later, we describe a slightly more elaborate procedure that is closer to our eventual construction.
We make the first and last block special in that they only contain an original section, and no transfer section. This ensures, for instance, that the minimum and maximum array elements are always in the first and last position respectively, a property that will be important later in the recursive data structure. So, the hole is moved to the end of T T T in the penultimate block, and then filled by the minimum element of the last block. Finally, the hole is moved from the beginning to the end of the last block by naïvely shifting O ( n ) O(\sqrt{n}) O ( n ) elements.
We use a more elaborate process for the initial positioning of the hole at the end of a transfer block. If the hole is in an original section, we first move it to the end of its section by shifting elements. Next, we fill this hole with the minimum element of the transfer section, which moves the hole to the beginning of the transfer section. Finally, the hole is moved by shifting elements to the end of the transfer section, at which point the cascade of moves through the sequence of blocks can happen. (We also need some special cases when the transfer section is empty, or if the hole is in the first block, but we omit these from this description because the two-level data structure only serves an intuitive purpose for us.) An illustration of how a hole moves through the array is shown in Figure 1 .
When a deletion occurs in one of the original blocks, we route the resulting hole to the end of the last block and transfer its cell to a separate sorted suffix. New elements are inserted into this suffix, which we maintain in sorted order. Deletions within the suffix are handled using a simple shift to the end of the suffix. After every n \sqrt{n} n updates, we sort the entire array, resetting this suffix to empty. Note, that the last original block is initially given enough cells to ensure that it remains nonempty until the next time we sort the array. Clearly, each insertion or deletion only incurs O ( n ) O(\sqrt{n}) O ( n ) recourse, and the re-sorts also incur O ( n ) O(\sqrt{n}) O ( n ) amortized recourse per step. Importantly, we can bound the cost due to relaxation of sorted order.
The original blocks remain ordered by value, while each intermediate block consists of two sorted sections in reverse value order. Within each block, this introduces an additional cost of at most a constant multiple of its value range. Since the value ranges of different original blocks are disjoint, their total length is at most the value range of the entire array. The sorted suffix and its boundary with the preceding block contribute at most another constant of the overall value range. Thus, the sorting cost remains within a constant factor of the cost of a sorted array.
Our goal, in Theorem 1 is to adopt this idea but improve the recourse bound from O ( n ) O(\sqrt{n}) O ( n ) to O ( polylog ( n ) ) O(\operatorname{polylog}(n)) O ( polylog ( n )) , while incurring O ( polylog ( n ) ) O(\operatorname{polylog}(n)) O ( polylog ( n )) cost. A natural idea to do this is to generalize the 2-level structure to a d d d -level structure, where d = O ( log n ) d = O(\log n) d = O ( log n ) . We organize the array into recursively defined sections containing either one or three blocks, rather than using many blocks at a level. The main complication is that whereas a hole was moving across a sequence of blocks previously, it will now need to be moved through the last block by descending through its recursive structure. While this still uses the high-level idea of the 2-level operation, making this recursive process efficient is technically complicated. In particular, the resulting ordering constraints between the different sections at different levels of recursion are more delicate; in fact, the transfer section of the middle block need no longer be smaller than every element of the last block. The next two sections of the paper are devoted to describing a general d d d -level data structure that adopts some ideas from the 2-level data structure and eventually establishes Theorem 1 .
Dynamic Sorting Trees (DST)
For online sorting with fully dynamic updates, we propose a new data structure called an Augmented Dynamic Sorting Tree (A-DST). The A-DST determines how elements are moved within the array in response to insertions and deletions. To describe it, we first introduce a simpler data structure called a Dynamic Sorting Tree (DST), which will serve as its main building block.
A DST is a recursive organization of the array that keeps its elements approximately sorted while supporting the routing of holes. A hole is an empty cell created by deleting an element. Our goal is to move a hole to the last cell of the DST using few element movements, rather than shifting all the elements that follow it.
We define two operations for routing holes. The ANY2END operation moves a hole from an arbitrary position to the last cell of a DST. The START2END operation handles the special case where the hole is initially in the first cell, and does so more efficiently. We show that these operations require O ( d 3 ) O(d^3) O ( d 3 ) and O ( d 2 ) O(d^2) O ( d 2 ) element movements, respectively, apart from the occasional rebuilding needed to maintain the recursive structure. The recourse incurred in rebuilding will be accounted for in the amortized analysis of the A-DST.
We next describe the recursive structure of the DST and the operations used to maintain it.
Description of a d d d -Level DST
A dynamic sorting tree (DST) is a recursively partitioned array designed to support the routing of holes while keeping its elements approximately sorted. We define its structure recursively: for i > 1 i > 1 i > 1 , an i i i -level DST is partitioned into contiguous blocks, each consisting of sections that are themselves ( i − 1 ) (i-1) ( i − 1 ) -level DSTs. The recursion terminates at level 1, where a DST is simply a sorted array.
Blocks and sections. For d ≥ 2 d \ge2 d ≥ 2 , a d d d -level DST consists of either one or three consecutive level-( d − 1 ) (d-1) ( d − 1 ) blocks . Every block contains an original section , and a middle block also contains a transfer section , which may be empty. Each nonempty section is itself a ( d − 1 ) (d-1) ( d − 1 ) -level DST. Elements are called original or transfer according to the section in which they reside. If the DST consists of a single block, that block contains only an original section, and its size may grow or shrink over time. Otherwise, the three blocks are called the first , middle , and last blocks, in left-to-right order.
Middle block. The transfer section precedes the original section and is empty when the block is built. Between rebuilds, the original section can only shrink and the transfer section can only grow. Their combined size, and hence the size of the block, remains fixed.
First and last blocks. Each consists only of an original section and has no transfer section. The sizes of these blocks may grow or shrink over time.
Thus, a three-block section has the form O 1 ∣ T 2 O 2 ∣ O 3 O_1 \mid T_2 O_2 \mid O_3 O 1 ∣ T 2 O 2 ∣ O 3 , as illustrated in Figure 2 .
Figure 2. A three-block d d d -level DST for d ≥ 3 d \ge3 d ≥ 3 . Original sections are gray and transfer sections blue. The lower row expands O 3 O_3 O 3 into its three-block structure at level d − 1 d-1 d − 1 .
Holes, levels, and the tree view. A DST contains no holes in its steady state, but may temporarily contain a single hole while executing a hole-routing operation.
We view an i i i -level DST as a level-i i i section. Unrolling the recursive decomposition gives a rooted tree whose nodes alternate between sections and blocks. The root is the level-d d d section corresponding to the entire DST (see Figure 3 ).
Figure 3. Tree view of a three-level DST, with the subtree rooted at O 3 O_3 O 3 expanded. Original sections are gray and transfer sections blue. The ordering O 1 ′ < T 2 < O 2 ′ O'_1 < T_2 < O'_2 O 1 ′ < T 2 < O 2 ′ relates sections at different levels. Other subtrees are omitted.
For i ≥ 2 i \ge2 i ≥ 2 , each nonempty level-i i i section has either one or three level-( i − 1 ) (i-1) ( i − 1 ) blocks as children, ordered from left to right. Each level-i i i block, in turn, has its constituent level-i i i sections as children. A middle block has two children: its transfer section followed by its original section. The transfer child is retained even when it is empty. A first, last, or singleton block has a single child, corresponding to its original section. The level-1 sections are sorted arrays. Arranged from left to right, these arrays constitute the underlying array. We use this tree to describe relationships between blocks and sections. The parent of a level-i i i block is the level-( i + 1 ) (i+1) ( i + 1 ) section containing it, while the parent of a nonroot level-i i i section is the level-i i i block containing it. Two nodes with the same parent are called siblings , and their order is inherited from the underlying array.
Roadmap for the remainder of the section. Having described the recursive structure of a DST, we next present its structural invariants in § 4.2 and use them to establish the cost bound in Lemma 8.
In § 4.3 , we introduce the operations supported by a DST, specifying their behavior and dependencies without yet describing their implementations. We then describe the basic operations InsertMax, ReBuild, and SwapHole in § 4.4 .
Finally, in § 4.5 , we give the implementations of the hole-routing operations, starting with JumpDown and SimpleStart2End, followed by Start2End and Any2End. We establish their correctness and recourse bounds alongside their implementations. The recourse incurred by ReBuild is accounted for separately in the amortized analysis of the A-DST in § 5 .
The Structural Invariants
The DST satisfies the following structural invariants between updates. We assume without loss of generality that all element values are distinct, using infinitesimal perturbations to break ties.
For two sets of elements A A A and B B B , we write A < B A < B A < B if every element of A A A is smaller than every element of B B B . We use the same notation for sections, comparing the elements they contain. Comparisons involving an empty set are vacuous.
Number and Structure of Blocks. Every level-i i i section with i ≥ 2 i \ge2 i ≥ 2 consists of either one or three level-( i − 1 ) (i-1) ( i − 1 ) blocks. A single block contains only an original section, denoted by O O O .
In a three-block section, the blocks are, from left to right, the first, middle, and last blocks. The first and last blocks contain only original sections, while the middle block contains a transfer section followed by an original section. Thus, a three-block section has the form O 1 ∣ T 2 O 2 ∣ O 3 O_1 \mid T_2 O_2 \mid O_3 O 1 ∣ T 2 O 2 ∣ O 3 . The transfer section may be empty, but the original section of every middle block contains at least one element.
Base-Level Sorting. Every level-1 section is sorted in increasing order from left to right.
Block Sizes. For a section consisting of level-i i i blocks, the size bounds are as follows:
If the section consists of a single block, its size is at most 12 ⋅ 2 i 12 \cdot2^i 12 ⋅ 2 i .
If the section consists of three blocks, the middle block has size exactly 2 i 2^i 2 i , the first block has size in [ 2 i , 12 ⋅ 2 i ) [2^i, 12 \cdot2^i) [ 2 i , 12 ⋅ 2 i ) , and the last block has size in [ 7 ⋅ 2 i , 12 ⋅ 2 i ) [7 \cdot2^i, 12 \cdot2^i) [ 7 ⋅ 2 i , 12 ⋅ 2 i ) .
These bounds imply that, in a three-block section, the original section of the last block also consists of three blocks unless it is at level 1. Indeed, a last level-i i i block with i > 1 i > 1 i > 1 owns at least 7 ⋅ 2 i 7 \cdot2^i 7 ⋅ 2 i cells. If its original section consisted of a single level-( i − 1 ) (i-1) ( i − 1 ) block, it would own at most
12 ⋅ 2 i − 1 = 6 ⋅ 2 i < 7 ⋅ 2 i 12 \cdot2^{i-1} = 6 \cdot2^i < 7 \cdot2^i 12 ⋅ 2 i − 1 = 6 ⋅ 2 i < 7 ⋅ 2 i
cells, a contradiction.
Block Ordering. Consider a three-block section O 1 ∣ T 2 ∣ O 2 ∣ O 3 O_1 \mid T_2 \mid O_2 \mid O_3 O 1 ∣ T 2 ∣ O 2 ∣ O 3 . We require O 1 < O 2 < T 2 O_1 < O_2 < T_2 O 1 < O 2 < T 2 and O 2 < O 3 O_2 < O_3 O 2 < O 3 .
If O 3 O_3 O 3 is a level-1 section, we additionally require T 2 < O 3 T_2 < O_3 T 2 < O 3 . Otherwise, the block-size bounds ensure that O 3 O_3 O 3 consists of three blocks. Writing O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ O_3 = O'_1 \mid T'_2 \mid O'_2 \mid O'_3 O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ , we require O 1 ′ < T 2 < O 2 ′ O'_1 < T_2 < O'_2 O 1 ′ < T 2 < O 2 ′ . Since O 2 ′ O'_2 O 2 ′ is nonempty, the ordering conditions within O 3 O_3 O 3 also give
O 1 ′ < T 2 < ( T 2 ′ ∪ O 2 ′ ∪ O 3 ′ ) . O'_1 < T_2 < (T'_2 \cup O'_2 \cup O'_3). O 1 ′ < T 2 < ( T 2 ′ ∪ O 2 ′ ∪ O 3 ′ ) .
The ordering invariants give the following property of the minimum element.
Claim 6. In every nonempty i i i -level DST, the minimum element occupies the leftmost cell.
They also give the corresponding property for the maximum element.
Claim 7. In every nonempty i i i -level DST, the maximum element occupies the rightmost cell.
Sorting-cost bound. The ordering invariants also bound the sorting cost of a DST.
Lemma 8. Let S S S be an i i i -level DST. Then, for every threshold z z z , we have cross z ( S ) ≤ 4 i \operatorname{cross}_z(S) \le4i cross z ( S ) ≤ 4 i . Consequently, if all elements of S S S lie in an interval I I I , then we have cost ( S ) ≤ 4 i ⋅ ∣ I ∣ \operatorname{cost}(S) \le4i \cdot|I| cost ( S ) ≤ 4 i ⋅ ∣ I ∣ .
Overview of Operations and Inter-dependencies
The structural invariants guarantee the sorting-cost bound. It remains to implement the operations while preserving these invariants. We first specify the interface that a DST provides to the surrounding A-DST (§ 5 ), and then describe the implementation.
Interface. A DST supports two operations that are invoked by the surrounding A-DST:
Any2End: Given a DST with a hole in an arbitrary position, this operation moves the hole to its last position. An A-DST uses this operation to move the hole to the end of a DST where a deletion occurs in.
Start2End: Given a DST with a hole in its first position, this operation moves the hole to its last position. An A-DST uses this operation to pass a hole through a sequence of DSTs.
Note that Any2End is more general than Start2End, which only moves a hole from the beginning of a DST to its end. Indeed, Any2End will use Start2End in its implementation.
Auxiliary Operations and Inter-dependencies. The two main operations that move a hole within a DST, Start2End and Any2End, use two auxiliary operations internal to a DST, which we describe next.
First, we distinguish a special case of Start2End that is used internally by Start2End, and is more efficient than a generic Start2End operation:
Finally, all the previous operations need to move a hole within the unique original section of the last block.
We describe this next:
In Figure 4 , we show the structure of auxiliary calls between these operations. Each arrow indicates that the operation at the head calls the operation at the tail of the arrow. We note that there are no cyclic sequence of calls, which means that in order to ensure that each operation terminates, we need to only ensure that the recursion within each operation is well-defined.
Figure 4. The interface operations of a DST and their auxiliary dependencies. The interface operations Any2End and Start2End have green borders. Recursive calls to the same operation are not shown.
For each operation, all recursive calls issued for a level-i i i DST are to level-j j j DSTs for j < i j < i j < i . Note that this is not to say that all auxiliary operations called within an operation are to DSTs at a lower level. In fact, several operations will call other operations at the same recursive level. But, this does not affect finite termination because each call either moves forward on the DAG in Figure 4 or reduces the level of the DST. Eventually, the only base cases are for level-1 DSTs, which are sorted arrays.
Given the somewhat complicated structure of the recursion, we sometimes explicitly mention the level of the DST on which an operation is being called. While the input to the operation is simply a DST, explicitly writing the level makes it clear to the reader that the recursion satisfies the condition of decreasing the level in each recursive call.
Basic Operations and Rebuilding
We start our detailed descriptions of the implementation of the DST operations by first describing some basic operations that will be used by all the operations specified above that actually move a hole within a DST.
The InsertMax operation. Given a DST whose last position is a hole, and an element y y y larger than every element currently stored in the DST, this operation places y y y in the hole.
Claim 9. The InsertMax operation maintains all structural invariants of the DST.
The operation moves only y y y into the hole. All other elements remain in place.
Claim 10. The recourse of InsertMax is 1.
The ReBuild operation. Moving a hole across the boundary between two adjacent DSTs changes their sizes. Such changes may violate the Block Sizes invariant of § 4.2 . To repair these violations, we introduce the ReBuild operation, which reorganizes the affected part of the structure.
Given a DST D D D requiring rebuilding, ReBuild selects a DST to reconstruct according to the rules below. This may be a larger enclosing DST when necessary to preserve the ordering invariants. The operation sorts the stored elements and reconstructs the recursive structure, with all transfer sections empty. If the selected DST contains a hole, it is placed at the end of the DST. Rebuilding preserves the total number of cells, and the hole counts toward the block sizes just like any occupied cell. The ReBuild operation is defined as follows.
For a level-1 DST, we simply sort its stored elements.
For a level-( i + 1 ) (i+1) ( i + 1 ) DST D D D , where i ≥ 1 i \ge1 i ≥ 1 , we first consider the sizes of its constituent blocks. If they satisfy the Block Sizes invariant, we preserve the number and sizes of these blocks, but not necessarily their contents. Otherwise, we choose a new block division as follows: if ∣ D ∣ ≤ 11 ⋅ 2 i |D| \le11 \cdot2^i ∣ D ∣ ≤ 11 ⋅ 2 i , we create a single block. Otherwise, we create three blocks, where the middle contains exactly 2 i 2^i 2 i cells, the last contains
max { 8 ⋅ 2 i , ⌈ ∣ D ∣ − 2 i 2 ⌉ } \max\left\{8 \cdot2^i,\left\lceil\frac{|D|-2^i}{2}\right\rceil\right\} max { 8 ⋅ 2 i , ⌈ 2 ∣ D ∣ − 2 i ⌉ }
cells, and the first contains the remaining cells.
In either case, we sort all the elements of D D D and distribute them among the original sections of the blocks in increasing order, according to the designated block sizes. The transfer section of the middle block, if present, is made empty. If D D D contains a hole, we treat it as the largest element, so that it occupies the last cell of D D D . As before, the hole counts toward block sizes.
We then apply ReBuild recursively to each original section, rebuilding its constituent DST all the way down to level 1. This recursion is performed regardless of whether the block division was changed.
Claim 11. The ReBuild operation maintains all structural invariants of the DST.
Rebuilding moves elements only within the selected DST, which contains O ( 2 i ) O(2^i) O ( 2 i ) cells at level i i i .
Claim 12. The worst-case recourse of ReBuild on a level-i i i DST is O ( 2 i ) O(2^i) O ( 2 i ) .
The SwapHole operation. To move a hole through the recursive structure of a DST, we sometimes need to transfer an empty cell between adjacent sections. In particular, this occurs between the transfer and original sections of a middle block, which are represented by adjacent DSTs.
The SwapHole operation performs this transfer by changing which section owns the empty cell, without moving any stored element. However, changing the sizes of the sections may violate the structural invariants, which we restore using ReBuild.
The operation is implemented as follows.
Let D D D and D ′ D' D ′ denote the DSTs supplying and receiving the hole, respectively. Suppose D D D is immediately to the left of D ′ D' D ′ , and its last cell h h h contains the hole. We remove h h h from D D D and make it the first cell of D ′ D' D ′ .
This is done recursively along the chains of last original sections of D D D and first original sections of D ′ D' D ′ , down to level 1. A transfer in the opposite direction is symmetric.
After transferring the hole, we examine the affected sections and their ancestors, from highest level to lowest. A section requires repair if a Block Size invariant is violated or if it has three blocks and its middle original section becomes empty.
Let S S S be the highest-level section requiring repair. We apply ReBuild to S S S , unless S S S is the last original section of a three-block parent P P P , in which case we rebuild P P P instead. This empties the transfer section of P P P , removing the ordering constraint that rebuilding S S S might violate. Since P P P was examined before S S S , its block sizes are valid and are preserved by ReBuild.
We repeat until all affected sections satisfy the structural invariants.
Claim 13. The SwapHole operation maintains all structural invariants of the DSTs.
Implementation Details of Operations that Move a Hole
Now, we give detailed implementations of the operations that move a hole within a DST. These operations use the previously defined basic operations, InsertMax and SwapHole, along with calling each other according to Figure 4 (and recursively calling themselves at lower levels). To keep this description organized, we first describe the two simpler operations, JumpDown and SimpleStart2End, and then the more complex ones, Start2End and Any2End.
Remark. Several of the operations we describe below will call SwapHole, and therefore might trigger ReBuild. If this happens, ReBuild may change the recursive decomposition and move the hole to the end of the DST it was called from, or even to the end of a higher-level DST containing it. In this case, all the operation calls for which the hole has already moved to the end of its DST are truncated since they do not need to execute their remaining steps. (Note that the purpose of all the operations moving a hole are to bring the hole at the end of the DST they are called from.)
The Simpler Operations: JumpDown and SimpleStart2End
We begin with the two operations for moving holes that are already at the boundaries of recursive sections. The main idea is to move a hole through a section by transferring only a few elements, rather than shifting the entire section.
Figure 5. Two steps of JumpDown (i i i ) through the expanded last sections O 3 O_3 O 3 and O 3 ′ O'_3 O 3 ′ . Red outlines mark holes and green cells mark the next elements to move. After each transfer, SwapHole assigns the vacated cell to the preceding transfer section. The hole passes from T 2 T_2 T 2 to T 2 ′ T'_2 T 2 ′ and then to T 2 ′ ′ T''_2 T 2 ′′ .
The JumpDown operation. Consider a three-block section S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 S = O_1 \mid T_2 \mid O_2 \mid O_3 S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . Suppose the hole is at the end of T 2 T_2 T 2 . We would like to fill it with an element from O 3 O_3 O 3 , but min O 3 \min O_3 min O 3 may be smaller than the elements of T 2 T_2 T 2 . Instead, consider the three-block structure of O 3 O_3 O 3 , given by O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ O_3 = O'_1 \mid T'_2 \mid O'_2 \mid O'_3 O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ . The ordering invariant O 1 ′ < T 2 < O 2 ′ O'_1 < T_2 < O'_2 O 1 ′ < T 2 < O 2 ′ allows us to move min O 2 ′ \min O'_2 min O 2 ′ into the hole. We then use SwapHole to move the resulting hole to the end of T 2 ′ T'_2 T 2 ′ , without moving any additional elements. This brings the hole to the analogous position of its starting location, but in a DST at a lower level. So, we can now recurse on T 2 ′ T'_2 T 2 ′ .
Formally, the JumpDown operation is implemented recursively as follows:
If O 3 O_3 O 3 is a level-1 DST, move min O 3 \min O_3 min O 3 into the hole in T 2 T_2 T 2 using InsertMax, and shift the elements of O 3 O_3 O 3 one position to the left to move the hole to the end of O 3 O_3 O 3 .
Otherwise, we perform the following steps: (a) Move min O 2 ′ \min O'_2 min O 2 ′ into the hole in T 2 T_2 T 2 using InsertMax. (b) Apply SwapHole (O 2 ′ O'_2 O 2 ′ , T 2 ′ T'_2 T 2 ′ ) from right to left, transferring the hole to the end of T 2 ′ T'_2 T 2 ′ . (c) Invoke JumpDown (i − 1 i - 1 i − 1 ) on O 3 O_3 O 3 , moving the hole to the end of S S S .
As in all operations, if rebuilding has already moved the hole to the end of S S S or an enclosing section, the corresponding unfinished operations terminate.
Claim 14. The JumpDown operation preserves all structural invariants and moves the hole to the last position of the DST.
The hole descends through at most i i i levels, with O ( 1 ) O(1) O ( 1 ) recourse per level apart from rebuilding.
Claim 15. Excluding recourse incurred by any ReBuild calls, JumpDown (i i i ) incurs O ( i ) O(i) O ( i ) recourse.
Proof. We prove the claim by induction on i i i . The base case shifts elements in a level-2 DST, since O 3 O_3 O 3 is a level-1 DST. Since a level-2 DST has O ( 1 ) O(1) O ( 1 ) elements this incurs O ( 1 ) O(1) O ( 1 ) recourse. In the inductive case, we move one element from O 2 ′ O'_2 O 2 ′ into T 2 T_2 T 2 using InsertMax (recourse of 1 by Claim 10 ) and then apply SwapHole which only incurs recourse if it calls ReBuild; the latter recourse is explicitly omitted from this claim. Finally, we recursively call JumpDown (i − 1 i - 1 i − 1 ). Thus, excluding ReBuild, the recourse satisfies R ( i ) ≤ R ( i − 1 ) + O ( 1 ) R(i) \le R(i - 1) + O(1) R ( i ) ≤ R ( i − 1 ) + O ( 1 ) , where R ( 1 ) = O ( 1 ) R(1) = O(1) R ( 1 ) = O ( 1 ) . The claim follows. □ \square □
The SimpleStart2End operation. To move a hole from the beginning to the end of S S S , we first move it recursively through O 1 O_1 O 1 . We then fill it with min O 2 \min O_2 min O 2 , leaving a hole at the beginning of O 2 O_2 O 2 . Using SwapHole, we move this hole to the end of T 2 T_2 T 2 without moving any elements. We can now apply JumpDown to complete the movement to the end of S S S .
Formally, the operation is implemented recursively as follows.
If i = 1 i = 1 i = 1 , shift the elements of the sorted array to move the hole to its last position.
If S S S contains a single block with original section O O O , invoke SimpleStart2End ( i − 1 ) (i - 1) ( i − 1 ) on O O O .
Otherwise, write S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 S = O_1 \mid T_2 \mid O_2 \mid O_3 S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 and perform the following steps: (a) Apply SimpleStart2End ( i − 1 ) (i - 1) ( i − 1 ) to O 1 O_1 O 1 , moving the hole to the end of O 1 O_1 O 1 . (b) Move min O 2 \min O_2 min O 2 into the hole in O 1 O_1 O 1 using InsertMax. (c) Apply SwapHole ( O 2 , T 2 ) (O_2,T_2) ( O 2 , T 2 ) from right to left, moving the hole to the end of T 2 T_2 T 2 . (d) Finally, apply JumpDown ( i ) (i) ( i ) to move the hole to the end of S S S .
We illustrate this operation in Figure 6 .
Figure 6. SimpleStart2End ( i ) (i) ( i ) on S = O 1 ∣ T 2 O 2 ∣ O 3 S = O_1 \mid T_2 O_2 \mid O_3 S = O 1 ∣ T 2 O 2 ∣ O 3 , without rebuilding. After the hole reaches the end of O 1 O_1 O 1 , InsertMax fills it with min ( O 2 ) \min(O_2) min ( O 2 ) . The vacated cell becomes part of T 2 T_2 T 2 under SwapHole, and JumpDown moves the hole to the end of S S S .
Claim 16. The SimpleStart2End operation moves the hole from the first to the last position of the DST, while preserving all structural invariants.
As the recursion returns through level j j j , it performs O ( 1 ) O(1) O ( 1 ) local movements and calls JumpDown ( j ) (j) ( j ) . Excluding rebuilding, the resulting O ( j ) O(j) O ( j ) recourse per level sums to O ( i 2 ) O(i^2) O ( i 2 ) .
Claim 17. Excluding recourse incurred by any ReBuild calls, SimpleStart2End ( i ) (i) ( i ) incurs O ( i 2 ) O(i^2) O ( i 2 ) recourse.
Proof. The first base case is on O ( 1 ) O(1) O ( 1 ) -sized level-1 DST incurring O ( 1 ) O(1) O ( 1 ) recourse. The second base case is dominated by the inductive case, which incurs O ( i ) O(i) O ( i ) recourse for JumpDown ( i ) (i) ( i ) (by Claim 15), O ( 1 ) O(1) O ( 1 ) recourse for InsertMax (by Claim 10), and no recourse for SwapHole excluding ReBuild calls. Since SimpleStart2End ( i ) (i) ( i ) makes one recursive call to SimpleStart2End ( i − 1 ) (i-1) ( i − 1 ) , we get R ( i ) ≤ R ( i − 1 ) + O ( i ) R(i) \le R(i-1) + O(i) R ( i ) ≤ R ( i − 1 ) + O ( i ) . The claim follows.
The Complex Operations: Start2End and Any2End
The operations JumpDown and SimpleStart2End described above do not yet handle all situations of moving a hole through a DST. First, recall that SimpleStart2End does not handle the case when the DST S S S is the (unique) section of the last block of its parent. We will handle this explicitly in the Start2End operation, which will include all cases of moving a hole from the beginning to the end of a DST. Second, a deletion may create a hole at an arbitrary position of a DST, and not at the beginning of the DST. In Any2End, we will generalize Start2End to handling the case when the hole is initially in an arbitrary position of the array. Later, we will use Any2End to implement an element deletion in the Delete operation of the A-DST.
The Start2End operation. The main difficulty beyond SimpleStart2End arises when a DST S S S is the last original section of a three-block parent S ^ \widehat{S} S with a nonempty transfer section. In this case, write
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 , S ^ = O ^ 1 ∣ T ^ 2 ∣ O ^ 2 ∣ S . S = O_1 \mid T_2 \mid O_2 \mid O_3,\qquad\widehat{S} = \widehat{O}_1 \mid\widehat{T}_2 \mid\widehat{O}_2 \mid S. S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 , S = O 1 ∣ T 2 ∣ O 2 ∣ S .
The ordering invariants require
O 1 < T ^ 2 < O 2 . O_1 < \widehat{T}_2 < O_2. O 1 < T 2 < O 2 .
Thus, we cannot move min O 2 \min O_2 min O 2 directly into O 1 O_1 O 1 , as in SimpleStart2End. Instead, we move min T ^ 2 \min\widehat{T}_2 min T 2 into O 1 O_1 O 1 , route the resulting hole through T ^ 2 \widehat{T}_2 T 2 using SimpleStart2End, and fill it with min O 2 \min O_2 min O 2 . The remaining steps are then identical to SimpleStart2End. Figure 7 illustrates these recursive movements.
Figure 7. Recursive execution of Start2End (i i i ) when S S S is its parent’s last original section and T ^ 2 \hat{T}_2 T ^ 2 is nonempty. Each SimpleStart2End descends to level 1; on returning to level j j j , it performs O ( 1 ) O(1) O ( 1 ) local work and calls JumpDown (j j j ). These repeated descents give O ( ( i − 1 ) 2 ) O((i-1)^2) O (( i − 1 ) 2 ) and O ( i 2 ) O(i^2) O ( i 2 ) recourse in the first two phases, followed by O ( i ) O(i) O ( i ) in the third. Gray arrows show recursive calls and returns; orange and dark blue arrows show local movements and JumpDown, respectively.
Formally, the Start2End operation is implemented recursively as follows:
If i = 1 i = 1 i = 1 , shift the elements of the sorted array to move the hole to its last position.
If S S S contains a single block with original section O O O , call Start2End ( i − 1 ) (i-1) ( i − 1 ) on O O O .
Otherwise, S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 S = O_1 \mid T_2 \mid O_2 \mid O_3 S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 is a three-block DST. If S S S is not the last original section of a three-block parent, call SimpleStart2End ( i ) (i) ( i ) on S S S .
Otherwise, S = O ^ 3 S = \widehat{O}_3 S = O 3 is the last original section of a three-block parent S ^ = O ^ 1 ∣ T ^ 2 ∣ O ^ 2 ∣ S \widehat{S} = \widehat{O}_1 \mid\widehat{T}_2 \mid\widehat{O}_2 \mid S S = O 1 ∣ T 2 ∣ O 2 ∣ S . In this case, we have the following steps:
(a) Apply SimpleStart2End ( i − 1 ) (i-1) ( i − 1 ) to O 1 O_1 O 1 , moving the hole to the end of O 1 O_1 O 1 . (Note that this is valid because O 1 O_1 O 1 is in first block in S S S .)
(b) We have two cases:
i. If T ^ 2 \widehat{T}_2 T 2 is empty, we move min O 2 \min O_2 min O 2 to the hole using InsertMax.
ii. Otherwise, T ^ 2 \widehat{T}_2 T 2 is non-empty. In this case, we do the following:
A. move min T ^ 2 \min\widehat{T}_2 min T 2 into O 1 O_1 O 1 using InsertMax.
B. apply SimpleStart2End ( i ) (i) ( i ) to T ^ 2 \widehat{T}_2 T 2 .
C. move the minimum element in O 2 O_2 O 2 into the resulting hole in T ^ 2 \hat{T}_2 T ^ 2 , using InsertMax.
(c) Apply SwapHole (O 2 , T 2 O_2,T_2 O 2 , T 2 ) from right to left, moving the hole to the end of T 2 T_2 T 2 .
(d) Finally, apply JumpDown (i i i ) to move the hole to the end of S S S .
As usual, if rebuilding has already moved the hole to the end of S S S or an enclosing section, the corresponding unfinished operations terminate.
Claim 18. The Start2End operation moves the hole from the first to the last position of the DST, while preserving all structural invariants.
Excluding rebuilding, the calls to SimpleStart2End contribute O ( i 2 ) O(i^2) O ( i 2 ) recourse in total, while the final call to JumpDown contributes only O ( i ) O(i) O ( i ) .
Claim 19. Excluding recourse incurred by any ReBuild calls, Start2End (i i i ) incurs O ( i 2 ) O(i^2) O ( i 2 ) recourse.
Proof. For i = 1 i=1 i = 1 , the operation shifts a sorted array of constant size, incurring O ( 1 ) O(1) O ( 1 ) recourse. For i > 1 i>1 i > 1 , if the DST consists of a single block, the operation recursively calls Start2End (i − 1 i-1 i − 1 ). The next case, which just calls SimpleStart2End (i i i ), subsumed by the the last case. In the last case, there are calls to SimpleStart2End (i i i ), SimpleStart2End (i − 1 i-1 i − 1 ), JumpDown (i i i ), and O ( 1 ) O(1) O ( 1 ) calls to InsertMax and SwapHole. By Claim 17, the calls to SimpleStart2End (i − 1 i-1 i − 1 ) and SimpleStart2End (i i i ) incur O ( ( i − 1 ) 2 ) O((i-1)^2) O (( i − 1 ) 2 ) and O ( i 2 ) O(i^2) O ( i 2 ) recourse, respectively. By Claim 15, the call to JumpDown (i i i ) incurs O ( i ) O(i) O ( i ) recourse. Finally, by Claim 10, the O ( 1 ) O(1) O ( 1 ) calls to InsertMax incur O ( 1 ) O(1) O ( 1 ) recourse, while SwapHole incurs no recourse aside from rebuilding. Thus, the total recourse is
O ( ( i − 1 ) 2 ) + O ( i 2 ) + O ( i ) + O ( 1 ) = O ( i 2 ) . O((i-1)^2) + O(i^2) + O(i) + O(1) = O(i^2). O (( i − 1 ) 2 ) + O ( i 2 ) + O ( i ) + O ( 1 ) = O ( i 2 ) .
Thus, writing R ( i ) R(i) R ( i ) for the recourse of Start2End ( i ) (i) ( i ) , excluding rebuilding, we obtain
R ( i ) ≤ max { R ( i − 1 ) , O ( i 2 ) } . R(i) \le\max\{R(i-1), O(i^2)\}. R ( i ) ≤ max { R ( i − 1 ) , O ( i 2 )} .
Together with R ( 1 ) = O ( 1 ) R(1) = O(1) R ( 1 ) = O ( 1 ) , this gives R ( i ) = O ( i 2 ) R(i) = O(i^2) R ( i ) = O ( i 2 ) .
The Any2End operation. Finally, we are left with the most general operation that moves a hole from an arbitrary position in a DST S S S to its end. To do this, we first move the hole recursively to the end of the section containing it within S S S (and therefore, one level lower than S S S ). The remaining movement depends on which section contains the hole in S S S .
If S S S has a single block, then we simply call Any2End recursively in its unique section. So, let us assume that S S S is a 3-block DST given by S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 S = O_1 \mid T_2 \mid O_2 \mid O_3 S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . The simplest case is when the hole is in O 3 O_3 O 3 , in which case it has already reached the end of S S S . Next, suppose the hole is in the middle block. If it is in T 2 T_2 T 2 , we use JumpDown to move it to the end of S S S . Otherwise, it is in O 2 O_2 O 2 , and we would like to fill the hole with min O 3 \min O_3 min O 3 and apply Start2End to O 3 O_3 O 3 . There is one case where we cannot do this directly: when T 2 T_2 T 2 is non-empty and O 3 O_3 O 3 is a level-1 DST. In this latter case, O 3 > T 2 > O 2 O_3 > T_2 > O_2 O 3 > T 2 > O 2 ; so, we cannot move min O 3 \min O_3 min O 3 to O 2 O_2 O 2 skipping T 2 T_2 T 2 . In this case, we move min T 2 \min T_2 min T 2 to the hole in O 2 O_2 O 2 , then apply SimpleStart2End to T 2 T_2 T 2 to move the hole to the end of this section, and finally apply JumpDown to move it to the end of S S S .
Finally, suppose the hole is in O 1 O_1 O 1 . Then, we use a subroutine similar to Start2End to move the hole to the end of S S S . The only difference with Start2End is that the latter starts with the hole at the beginning of O 1 O_1 O 1 rather than its end. But, the first step of Start2End moves the hole to the end of O 1 O_1 O 1 , before moving it further to the end of S S S . So, we simply copy the steps of Start2End omitting the first step.
Formally, the operation is implemented recursively as follows.
If i = 1 i = 1 i = 1 , shift the elements following the hole one position to the left.
If the DST contains a single block with original section O O O , call Any2End ( i − 1 ) (i - 1) ( i − 1 ) on O O O .
Otherwise, write S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 S = O_1 \mid T_2 \mid O_2 \mid O_3 S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . Let A A A denote the section containing the hole. First, call Any2End ( i − 1 ) (i - 1) ( i − 1 ) on A A A . We now have the following cases: (a) If A = O 3 A = O_3 A = O 3 , we end the operation. (b) If A = T 2 A = T_2 A = T 2 , call JumpDown ( i ) (i) ( i ) . (c) If A = O 2 A = O_2 A = O 2 , we distinguish two cases. i. If T 2 T_2 T 2 is nonempty and min T 2 < min O 3 \min T_2 < \min O_3 min T 2 < min O 3 (may only happen when O 3 O_3 O 3 is a level-1 section), move min T 2 \min T_2 min T 2 into the hole using InsertMax, apply SimpleStart2End ( i − 1 ) (i - 1) ( i − 1 ) to T 2 T_2 T 2 , and invoke JumpDown ( i ) (i) ( i ) . ii. Otherwise, move min O 3 \min O_3 min O 3 into the hole and apply Start2End ( i − 1 ) (i - 1) ( i − 1 ) to O 3 O_3 O 3 . (d) If A = O 1 A = O_1 A = O 1 , we proceed as follows:
Figure 8. The case of Any2End ( i ) (i) ( i ) in which S = O ^ 3 S = \widehat{O}_3 S = O 3 is the last original section of a three-block parent S ^ = O ^ 1 ∣ T ^ 2 ∣ O ^ 2 ∣ S \widehat{S} = \widehat{O}_1 \mid\widehat{T}_2 \mid\widehat{O}_2 \mid S S = O 1 ∣ T 2 ∣ O 2 ∣ S , and T ^ 2 \widehat{T}_2 T 2 is nonempty. Starting with the hole at the end of O 1 O_1 O 1 , the hole passes through T ^ 2 \widehat{T}_2 T 2 , returns to S S S , and then moves to the end of S S S . Red outlines mark holes; rebuilding is omitted.
i. There are two cases. Let S ^ \widehat{S} S be the level-( i + 1 ) (i+1) ( i + 1 ) DST that S S S is contained in.
Case 1: If S S S is the last original section of a three-block parent S ^ = O ^ 1 ∣ T ^ 2 ∣ O ^ 2 ∣ S \widehat{S} = \widehat{O}_1 \mid\widehat{T}_2 \mid\widehat{O}_2 \mid S S = O 1 ∣ T 2 ∣ O 2 ∣ S , and T ^ 2 \widehat{T}_2 T 2 is nonempty, then we:
A. Move min T ^ 2 \min\widehat{T}_2 min T 2 into the hole in O 1 O_1 O 1 using InsertMax.
B. Apply SimpleStart2End ( i ) (i) ( i ) to T ^ 2 \widehat{T}_2 T 2 .
C. Move min O 2 \min O_2 min O 2 into the resulting hole in T ^ 2 \widehat{T}_2 T 2 using InsertMax.
Case 2: Otherwise, we move min O 2 \min O_2 min O 2 into the hole in O 1 O_1 O 1 using InsertMax.
ii. Apply SwapHole ( O 2 , T 2 ) (O_2, T_2) ( O 2 , T 2 ) from right to left, moving the hole to the end of T 2 T_2 T 2 .
iii. Finally, apply JumpDown ( i ) (i) ( i ) to move the hole to the end of S S S .
Claim 20. The Any2End operation moves the hole from an arbitrary position to the last position of the DST, while preserving all structural invariants.
Summing the O ( j 2 ) O(j^2) O ( j 2 ) recourse at each level j j j , excluding rebuilding, gives the following bound.
Claim 21. Excluding recourse incurred by any ReBuild calls, Any2End ( i ) (i) ( i ) incurs O ( i 3 ) O(i^3) O ( i 3 ) recourse.
Proof. We prove the claim by induction on i i i . For i = 1 i = 1 i = 1 , the DST is a sorted array of constant size, so shifting the elements following the hole incurs O ( 1 ) O(1) O ( 1 ) recourse.
Now consider i > 1 i > 1 i > 1 . If the DST consists of a single block, the operation only calls Any2End ( i − 1 ) (i - 1) ( i − 1 ) , and the claim follows by induction. Otherwise, the operation first calls Any2End ( i − 1 ) (i-1) ( i − 1 ) on the section containing the hole. Depending on this section, the remaining steps involve either one call to Start2End, or a combination of one call to SimpleStart2End and also one call to JumpDown at level either i i i or i − 1 i-1 i − 1 , and O ( 1 ) O(1) O ( 1 ) calls to InsertMax and SwapHole.
By Claims 15, 17 and 19, these steps incur O ( i 2 ) O(i^2) O ( i 2 ) recourse, excluding rebuilding. The calls to InsertMax incur O ( 1 ) O(1) O ( 1 ) recourse, while SwapHole incurs no recourse apart from rebuilding. Thus, letting R ( i ) R(i) R ( i ) denote the recourse of Any2End ( i ) (i) ( i ) , excluding rebuilding, we obtain
R ( i ) ≤ R ( i − 1 ) + O ( i 2 ) , with R ( 1 ) = O ( 1 ) . R(i) \le R(i-1) + O(i^2), \text{ with } R(1) = O(1). R ( i ) ≤ R ( i − 1 ) + O ( i 2 ) , with R ( 1 ) = O ( 1 ) .
Summing over the levels gives
R ( i ) = O ( ∑ j = 1 i j 2 ) = O ( i 3 ) . R(i) = O\left(\sum_{j=1}^{i} j^2\right) = O(i^3). R ( i ) = O ( j = 1 ∑ i j 2 ) = O ( i 3 ) .
Fully-Dynamic Sorting (A-DST)
We now use the DST operations of § 4 to construct an augmented dynamic sorting tree (A-DST) that supports element insertions and deletions. This gives an O ( log 2 n ) O(\log^2 n) O ( log 2 n ) -competitive algorithm with O ( log 4 n ) O(\log^4 n) O ( log 4 n ) amortized recourse per update, proving Theorem 1.
Handling Insertions and Deletions: The A-DST
The DST of § 4 supports moving a hole through its recursive structure, but does not directly support insertions or deletions. We now use these operations to construct a data structure that supports both types of updates.
Our data structure, called an augmented dynamic sorting tree (A-DST), consists of a sequence of DSTs denoted D d , D d − 1 , … , D 2 D_d, D_{d-1}, \ldots, D_2 D d , D d − 1 , … , D 2 , where D j D_j D j is a level-j j j DST, followed by a sorted array, denoted A 1 A_1 A 1 (see Figure 9 ). We set d = 1 + ⌈ log 2 n ⌉ d = 1 + \lceil\log_2 n\rceil d = 1 + ⌈ log 2 n ⌉ . We call the constituent DSTs and the sorted array A 1 A_1 A 1 components of the overall A-DST. The components have geometrically decreasing size bounds, with D j D_j D j containing at most O ( 2 j ) O(2^j) O ( 2 j ) cells and A 1 A_1 A 1 containing O ( 1 ) O(1) O ( 1 ) cells. Any of these DSTs may be empty at any stage.
Figure 9. The components of a level-d d d A-DST. A level-j j j component has size O ( 2 j ) O(2^j) O ( 2 j ) . Insertions enter the sorted array A 1 A_1 A 1 , while deletions move holes toward the right end. Periodic reconstructions combine a component with the smaller components to its right.
By § 2 , insertions and deletions to an A-DST are alternated. Before insertion, the A-DST contains exactly one hole, which is at the end of A 1 A_1 A 1 . An insertion is performed in A 1 A_1 A 1 , maintaining its sorted order, shifting elements as required. In contrast, before deletion, the A-DST does not contain any hole. To delete an element, we first remove it from its cell, creating a hole. We then use the DST operations to move this hole to the end of its component and through the remaining components, until it reaches the end of the array. Finally, to prevent the smaller components from growing too large, we periodically reconstruct a component together with all components to its right. Such a reconstruction sorts their elements and builds a single DST at the corresponding level, leaving the smaller components empty.
We give details of the structure and operations of an A-DST below.
Description of a Level-d d d A-DST
We now formally define the recursive structure of the A-DST. Its recursion depth is d = 1 + ⌈ log 2 n ⌉ d = 1 + \lceil\log_2 n\rceil d = 1 + ⌈ log 2 n ⌉ , with levels indexed from 1 to d d d , where level d d d is the top level. For the base case, a level-1 A-DST is simply a sorted array of length n n n . Maintaining this order requires at most O ( n ) O(n) O ( n ) recourse per update and achieves a competitive ratio of 1.
For d > 1 d > 1 d > 1 , a level-d d d A-DST is partitioned into two contiguous regions: a level-d d d DST on the left and a level-( d − 1 ) (d-1) ( d − 1 ) A-DST on the right. Unrolling the recursion, a level-d d d A-DST consists of one level-i i i DST for each i = d , d − 1 , … , 1 i = d, d - 1, \ldots, 1 i = d , d − 1 , … , 1 , arranged in decreasing order of their levels. This structure of an A-DST is depicted in Figure 9 .
Structural invariants. Every component D j D_j D j satisfies the structural invariants of the DST in § 4.2 , and A 1 A_1 A 1 is sorted. We impose no ordering between different components. In addition, we maintain the following invariant:
Since D j D_j D j is contained in A j A_j A j , each component D j D_j D j contains at most 2 j 2^j 2 j elements. The same holds for D d D_d D d , since the entire array contains at most n ≤ 2 d n \le2^d n ≤ 2 d elements. In particular, A 1 A_1 A 1 contains at most two elements, so inserting into this sorted array incurs O ( 1 ) O(1) O ( 1 ) recourse, excluding any rebuilding.
Cost bound. We first bound the cost of an A-DST using the crossing bounds of its constituent DSTs. We then extend this guarantee to the subsequence of active elements, as required by the reduction in the preliminaries.
Claim 22. Let A A A be a level-i i i A-DST, and let A ′ A' A ′ be any subsequence of A A A . Then, for every threshold z z z ,
cross z ( A ′ ) ≤ 4 i 2 . \operatorname{cross}_z(A') \le4i^2. cross z ( A ′ ) ≤ 4 i 2 . Consequently, if all elements of A ′ A' A ′ lie in an interval I I I , then cost ( A ′ ) = O ( i 2 ) ⋅ ∣ I ∣ \operatorname{cost}(A') = O(i^2) \cdot|I| cost ( A ′ ) = O ( i 2 ) ⋅ ∣ I ∣ .
Proof. A level-i i i A-DST consists of one level-j j j DST for each j ∈ { 1 , … , i } j \in\{1,\ldots,i\} j ∈ { 1 , … , i } . By Lemma 8, each level-j j j DST contributes at most 4 j 4j 4 j crossings at any threshold z z z . In addition, there are at most i − 1 i-1 i − 1 boundaries between consecutive DSTs, each contributing at most one crossing. Thus,
cross z ( A ) ≤ ∑ j = 1 i 4 j + ( i − 1 ) = 2 i 2 + 3 i − 1 ≤ 4 i 2 . \operatorname{cross}_z(A) \le\sum_{j=1}^{i} 4j + (i-1) = 2i^2 + 3i - 1 \le4i^2. cross z ( A ) ≤ j = 1 ∑ i 4 j + ( i − 1 ) = 2 i 2 + 3 i − 1 ≤ 4 i 2 . Since A ′ A' A ′ is a subsequence of A A A , by Lemma 5,
cross z ( A ′ ) ≤ cross z ( A ) ≤ 4 i 2 . \operatorname{cross}_z(A') \le\operatorname{cross}_z(A) \le4i^2. cross z ( A ′ ) ≤ cross z ( A ) ≤ 4 i 2 . Integrating over I I I gives cost ( A ′ ) = O ( i 2 ) ⋅ ∣ I ∣ \operatorname{cost}(A') = O(i^2) \cdot|I| cost ( A ′ ) = O ( i 2 ) ⋅ ∣ I ∣ .
Maintaining the Recursive Structure
The Re-Sort (i i i ) Operation. As updates are performed, cells may be transferred from higher-level DSTs to lower-level DSTs, causing the latter to grow. To maintain the Suffix Sizes invariant, we periodically rebuild parts of the A-DST using Re-Sort.
For i ≥ 2 i \ge2 i ≥ 2 , the Re-Sort (i i i ) operation collects all elements of the level-i i i A-DST A i A_i A i , sorts them, and constructs an level-i i i DST containing these elements, leaving the level-( i − 1 ) (i-1) ( i − 1 ) A-DST empty.
Recall that each element update comprises a deletion followed by an insertion. For each i i i , we maintain a counter that counts the number of updates since the counter was last reset to 0. When the i i i th counter reaches 2 i − 1 2^{i-1} 2 i − 1 , we say that the A-DST A i A_i A i is ready for rebuilding. Rebuilding is performed after element insertion, i.e., at the end of the current update. If several levels require rebuilding simultaneously, we perform only the highest-level rebuilding and reset its counter and those of all lower levels. Rebuilding at level i i i is performed by calling Re-Sort (i i i ).
Claim 23. The Re-Sort operation maintains all structural invariants.
Each level contributes O ( 1 ) O(1) O ( 1 ) amortized rebuilding recourse per update. We obtain the following bound.
Claim 24. For a level-i i i A-DST, the amortized recourse incurred by Re-Sort is O ( i ) O(i) O ( i ) per update.
Proof. Consider Re-Sort (j j j ), for 2 ≤ j ≤ i 2 \le j \le i 2 ≤ j ≤ i . By the Suffix Sizes invariant, the level-j j j A-DST contains at most 2 j 2^j 2 j elements after each completed update. Immediately before rebuilding, its size may exceed this bound by at most one. Thus, Re-Sort (j j j ) incurs O ( 2 j ) O(2^j) O ( 2 j ) recourse.
The operation is invoked only after 2 j − 1 2^{j-1} 2 j − 1 updates since its counter was last reset, where each update consists of a deletion followed by an insertion. Hence its amortized recourse per update is
O ( 2 j ) 2 j − 1 = O ( 1 ) . \frac{O(2^j)}{2^{j-1}} = O(1). 2 j − 1 O ( 2 j ) = O ( 1 ) .
A higher-level rebuilding resets the counters of lower levels, which can only reduce their rebuilding frequency. Summing over the at most i i i levels gives O ( i ) O(i) O ( i ) amortized recourse per update. □
Transferring holes between components. We extend the SwapHole operation that we introduced earlier in DSTs to transfer a hole between two adjacent components of the A-DST, including the final sorted array A 1 A_1 A 1 . The transfer is performed by changing the boundary between the components, without moving any stored element. The implementation is as follows.
Let D D D and D ′ D' D ′ denote the components supplying and receiving the hole, respectively. Suppose D D D is immediately to the left of D ′ D' D ′ , and its last cell h h h contains the hole. We remove h h h from D D D and make it the first cell of D ′ D' D ′ . This is done recursively, removing h h h along the chain of last original sections of D D D and adding it along the chain of first original sections of D ′ D' D ′ , down to level 1.
After transferring the hole, we examine the affected sections and their ancestors, from highest level to lowest. A section requires repair if a Block Sizes invariant is violated or if it has three blocks and its middle original section becomes empty.
Let S S S be a highest-level section requiring repair. We apply Rebuild to S S S , unless S S S is the last original section of a three-block parent P P P , in which case we rebuild P P P instead. Rebuilding P P P empties its transfer section while preserving its top-level block sizes and the ordering constraints at higher levels.
When rebuilding a section in D ′ D' D ′ containing the hole, we treat the hole as the smallest element, leaving it in the first cell rather than the last. This convention also applies throughout the recursive rebuilding.
We repeat until all affected sections satisfy the DST invariants.
Since D D D and D ′ D' D ′ are separate components, they have no ordering constraints between them, and rebuilding is performed independently within each component. Moreover, the hole lies along the chain of first original sections of D ′ D' D ′ , so the rebuilding rule above preserves its position at the beginning of D ′ D' D ′ , as required by Start2End.
Claim 25. The SwapHole operation maintains all structural invariants of the A-DST.
We bound the total rebuilding recourse in terms of the number of calls to SwapHole.
Claim 26. At any point during the execution of a d d d -level A-DST, let M M M denote the number of SwapHole calls made so far. Then, the total recourse incurred by the resulting ReBuild operations is O ( d M ) O(dM) O ( d M ) .
A-DST: The interface
The interface of the A-DST contains two operations:
Delete: Given an element x x x stored in the A-DST, deletes x x x from the A-DST.
Insert: Given a new element x x x , inserts x x x into the A-DST.
Implementation of Delete (x x x ). The Delete (x x x ) operation removes an element x x x from a level-i i i A-DST and moves the resulting hole to its last position. The operation is implemented as follows.
Let D D D be the level-j j j component containing x x x , treating A 1 A_1 A 1 as a level-1 DST. Remove x x x from its cell, creating a hole, and apply Any2End (j j j ) to D D D to move the hole to its last position.
If D = A 1 D = A_1 D = A 1 , the operation is complete.
Otherwise, process the remaining components from left to right. For each such component D ′ D' D ′ : (a) Apply SwapHole (D , D ′ D,D' D , D ′ ) to transfer ownership of the hole to D ′ D' D ′ . (b) Apply Start2End to D ′ D' D ′ , moving the hole to its last position. (c) Set D = D ′ D = D' D = D ′ and continue to the next component.
Claim 27. The Delete operation maintains all structural invariants and moves the resulting hole to the last position of the A-DST.
Implementation of Insert (x x x ). Recall that each deletion is followed by an insertion. The deletion leaves a hole at the end of the A-DST, which belongs to its final level-1 sorted array. We insert x x x into its sorted position in this array, shifting the necessary elements to fill the hole.
Claim 28. The Insert (x x x ) operation maintains all structural invariants of the A-DST.
Finally, we get to proving the main lemma that shows the amortized recourse of the A-DST.
Lemma 29. The amortized recourse of Delete on a level-i i i A-DST is O ( i 4 ) O(i^4) O ( i 4 ) .
Proof. We first bound the recourse excluding ReBuild calls, and then bound the recourse due to ReBuild calls separately.
Suppose the deleted element belongs to a level-j j j component, where j ≤ i j \le i j ≤ i . By Claim 21, moving the resulting hole to the end of this component incurs O ( j 3 ) O(j^3) O ( j 3 ) recourse. We then apply Start2End to each of the remaining components. By Claim 19 , their total recourse is ∑ k = 1 j − 1 O ( k 2 ) = O ( j 3 ) \sum_{k=1}^{j-1} O(k^2) = O(j^3) ∑ k = 1 j − 1 O ( k 2 ) = O ( j 3 ) . Thus, the recourse of Delete, excluding ReBuild calls, is O ( i 3 ) O(i^3) O ( i 3 ) .
We next account for ReBuild calls. Consider a sequence of K K K deletions, and let M M M be the total number of calls to SwapHole during their execution. We distinguish between two types of SwapHole calls. Every internal SwapHole call within a DST is charged to the preceding InsertMax call that created the hole being transferred. Each such InsertMax call corresponds to a unit of recourse, which is charged at most once by SwapHole calls. Hence, the number of internal SwapHole calls is bounded by the recourse due to InsertMax calls, which is at most O ( K i 3 ) O(Ki^3) O ( K i 3 ) .
The remaining SwapHole calls transfer holes between adjacent components of the A-DST. Since there are only i i i components in an level-i i i A-DST, each Delete operation makes at most i − 1 i-1 i − 1 SwapHole calls of the second type. Cumulatively, the K K K element deletions make O ( K i ) O(Ki) O ( K i ) SwapHole calls.
Therefore, M = O ( K i 3 ) M = O(Ki^3) M = O ( K i 3 ) . By Claim 26 , these calls incur a total rebuilding recourse of O ( i M ) = O ( K i 4 ) O(iM) = O(Ki^4) O ( i M ) = O ( K i 4 ) . Therefore, the amortized recourse of Delete is O ( i 4 ) O(i^4) O ( i 4 ) , including ReBuild calls.
Cost Bound of A-DST
We use a d d d -level A-DST, where d = 1 + ⌈ log 2 ( n ) ⌉ d = 1 + \lceil\log_2(n) \rceil d = 1 + ⌈ log 2 ( n )⌉ . As described in § 2 , the A-DST always maintains n n n elements, some of which may be inactive.
Let A a c t i v e A_{\mathrm{active}} A active denote the subsequence of active elements, and let I I I be the interval they span. By Claim 22 ,
cost ( A a c t i v e ) = O ( d 2 ) ⋅ ∣ I ∣ . \operatorname{cost}(A_{\mathrm{active}}) = O(d^2) \cdot|I|. cost ( A active ) = O ( d 2 ) ⋅ ∣ I ∣.
Since O P T = ∣ I ∣ \mathrm{OPT} = |I| OPT = ∣ I ∣ and d = O ( log n ) d = O(\log n) d = O ( log n ) , the competitive ratio is O ( log 2 n ) O(\log^2 n) O ( log 2 n ) , as stated in Theorem 1 .
Recourse Bound of A-DST
By Lemma 29 , a Delete operation incurs O ( d 4 ) O(d^4) O ( d 4 ) amortized recourse. The subsequent insertion fills the hole at the end of A 1 A_1 A 1 . By the Suffix Sizes bound, including the temporary hole, this array has constant size. Inserting the new element in sorted order therefore incurs O ( 1 ) O(1) O ( 1 ) recourse and does not change the number of cells in any component. Finally, any scheduled Re-Sort is performed after the insertion. By Claim 24 , these Re-Sort calls contribute O ( d ) O(d) O ( d ) amortized recourse per update.
Thus, the amortized recourse per deletion-insertion pair is
O ( d 4 ) + O ( 1 ) + O ( d ) = O ( d 4 ) = O ( log 4 n ) , O(d^4) + O(1) + O(d) = O(d^4) = O(\log^4 n), O ( d 4 ) + O ( 1 ) + O ( d ) = O ( d 4 ) = O ( log 4 n ) ,
which is the recourse bound in Theorem 1 .
A Fully Dynamic Lower Bound
We now establish our lower bound on the amortized recourse required by deterministic fully dynamic sorting algorithms.
Theorem 2. Let 1 ≤ C ≤ O ( n ) 1 \le C \le O(n) 1 ≤ C ≤ O ( n ) . Any deterministic C C C -competitive algorithm for fully dynamic sorting with amortized recourse ρ \rho ρ satisfies
ρ = Ω ( log n log C + log n ) . \rho= \Omega\left(\frac{\log n}{\log C+\sqrt{\log n}}\right). ρ = Ω ( log C + log n log n ) .
We clarify that in Theorem 2, the condition C ≤ O ( n ) C \le O(n) C ≤ O ( n ) means that C ≤ c n C \le cn C ≤ c n for some constant c c c .
The instance
The initial instance contains one element of each value 0 , 1 n , 2 n , … , n − 1 n 0,\frac{1}{n},\frac{2}{n},\ldots,\frac{n-1}{n} 0 , n 1 , n 2 , … , n n − 1 , and every value that will be inserted into the array will have a value of 1. Hence, the optimum cost will always be at most 1. We organize the elements into a hierarchy of consecutive value ranges. The adversary will use this hierarchy to choose which elements to replace.
Let B ≥ 64 B \ge64 B ≥ 64 and d ≥ 1 d \ge1 d ≥ 1 be integers to be chosen later, with n = B d n = B^d n = B d . The hierarchy is represented by a complete B B B -ary tree T T T of depth d d d . Its leaves correspond, from left to right, to the elements x 0 , … , x n − 1 x_0,\ldots,x_{n-1} x 0 , … , x n − 1 . The root represents all elements, and each internal node divides its elements into B B B equal consecutive groups, one for each child, each leaf represents a single element.
Formally, for a node v v v , let X v X_v X v denote the set of original values represented by its descendant leaves, and let N v = ∣ X v ∣ N_v = |X_v| N v = ∣ X v ∣ . A node at depth ℓ \ell ℓ therefore satisfies
N v = B d − ℓ = n B ℓ . N_v = B^{d-\ell} = \frac{n}{B^\ell}. N v = B d − ℓ = B ℓ n .
If X v = { x a , … , x a + N v − 1 } X_v = \{x_a,\ldots,x_{a+N_v-1}\} X v = { x a , … , x a + N v − 1 } , associate with v v v the value interval
I v = [ a n , a + N v n ) , ∣ I v ∣ = N v n . I_v = \left[\frac{a}{n},\frac{a+N_v}{n}\right), \qquad|I_v| = \frac{N_v}{n}. I v = [ n a , n a + N v ) , ∣ I v ∣ = n N v .
Remark. We assume n = B d n = B^d n = B d for simplicity. For arbitrary n n n , a constant-factor smaller depth and rounding of B B B give B d = Θ ( n ) B^d = \Theta(n) B d = Θ ( n ) . Use the first B d B^d B d values for the tree and leave the others unreplaced outside its value interval. With population counts restricted to the tree’s values, only universal constants change in the proof.
The adversary
The adversary works in rounds, each consisting of a forward phase followed by a backward phase. Each round begins with the initial multiset of values
0 , 1 n , 2 n , … , n − 1 n . 0,\frac{1}{n},\frac{2}{n},\ldots,\frac{n-1}{n}. 0 , n 1 , n 2 , … , n n − 1 .
During the forward phase, the adversary searches the value tree to select an element to replace by a copy of 1. It restricts this search by controlling which children may be entered.
From now on we fix a single round. When an internal node is first visited, the adversary labels its children as targets , or buffers . Later, the buffer children are relabeled as released .
Labeling the children. When the search first reaches an internal node v v v during the forward phase, the adversary labels its children before continuing the search below v v v . This initial labeling is chosen once per node (in each round), using the algorithm’s current arrangement. At this point, all original values in X v X_v X v are still present, since no element below v v v has yet been selected for replacement during the round.
Let v 1 , … , v B v_1,\ldots,v_B v 1 , … , v B denote the children of v v v , ordered by value. The first and last B / 4 B/4 B /4 children are all labeled as buffers. The labels of the middle B / 2 B/2 B /2 children are chosen according to the positions of their elements in the array, as follows: List the N v / 2 N_v/2 N v /2 values belonging to the middle children as z 1 , … , z N v / 2 z_1,\ldots,z_{N_v/2} z 1 , … , z N v /2 , in the left-to-right order of the cells containing their elements. We partition this list into B / 16 B/16 B /16 consecutive groups of 8 N v / B 8N_v/B 8 N v / B values, where consecutive refers to the order in this list, not that they occupy consecutive array cells. We call these groups windows . For a given labeling of the middle children as either a target or as a buffer we call a window balanced if it contains at least N v / B N_v/B N v / B values from target children and at least N v / B N_v/B N v / B values from buffer children. We choose a labeling for the children for which the number of balanced windows is Ω ( B ) \Omega(B) Ω ( B ) (we show that such labeling exists).
Paid intervals and released children. Fix a constant ε > 0 \varepsilon> 0 ε > 0 , to be chosen later. For each visited internal interval I v I_v I v , the adversary counts the elements in its initially labeled buffer children that the algorithm has moved in updates after the labels were assigned. Each element is counted only once, even if it moves several times or returns to the cell it occupied when the labels were assigned.
At the end of each completed update of the forward phase, an interval I v I_v I v becomes paid if the number of buffer elements that the algorithm moved is at least ε N v \varepsilon N_v ε N v . When this happens, all its buffer children are relabeled as released for the rest of the forward phase.
The sequence. The adversary uses these labels to guide its search for the next element to replace. A target child is available for search, and a buffer child becomes available once it is relabeled as released. Each search starts at the root. At an internal node, the adversary first labels its children if it has not already done so during this round. It then searches target and released children in increasing value order, backtracking whenever it cannot reach a remaining element in a subtree. Leaves whose elements have already been removed (and replaced by 1) are skipped. When the search reaches a leaf whose element is still present, the adversary deletes that element and then inserts a new copy of 1.
The forward phase ends when there is no path from the root to a leaf containing an element through target and released nodes. Suppose the forward phase removed the values y 1 , … , y m y_1,\ldots,y_m y 1 , … , y m , in that order, and let e j e_j e j be the fresh copy of 1 inserted after the removal of y j y_j y j . The backward phase first deletes e 1 , … , e m e_1,\ldots,e_m e 1 , … , e m , in that order, and then reinserts y 1 , … , y m y_1,\ldots,y_m y 1 , … , y m , in that order. The algorithm responds to each deletion and insertion. This restores the initial multiset of values and completes the round.
The adversary then clears all child labels, payment statuses, and movement counts. The next round uses the same value tree and begins from the algorithm’s arrangement at the end of the backward phase. The adversary repeats this procedure for a number of rounds to be specified in the analysis.
The analysis
We first show that the labeling rule guarantees many balanced windows. To prove the bound, we consider a random labeling and bound the expected number of balanced windows. Some fixed labeling must achieve at least this expectation, and therefore so does the labeling chosen by the adversary.
Lemma 30. At every internal node v v v , there exists a labeling of the children for which at least a 7 / 9 7/9 7/9 -fraction of the windows are balanced.
Proof. Consider a random labeling in which each middle child is independently labeled as a target or a buffer, with probability 1 / 2 1/2 1/2 .
Fix a window, for each middle child v i v_i v i , let a i a_i a i be the number of its values in W W W . Each child contains N v / B N_v/B N v / B values in total, while W W W contains 8 N v / B 8N_v/B 8 N v / B values, so
0 ≤ a i ≤ N v / B , ∑ i a i = 8 N v / B . 0 \le a_i \le N_v/B,\qquad\sum_i a_i = 8N_v/B. 0 ≤ a i ≤ N v / B , i ∑ a i = 8 N v / B .
Let X X X be the number of values in W W W belonging to children labeled as targets. Since the child labels are independent,
E [ X ] = 1 2 ∑ i a i = 4 N v / B , \mathbb{E}[X] = \frac{1}{2}\sum_i a_i = 4N_v/B, E [ X ] = 2 1 i ∑ a i = 4 N v / B ,
and
Var ( X ) = 1 4 ∑ i a i 2 ≤ N v / B 4 ∑ i a i = 2 ( N v / B ) 2 . \operatorname{Var}(X) = \frac{1}{4}\sum_i a_i^2 \le\frac{N_v/B}{4}\sum_i a_i = 2(N_v/B)^2. Var ( X ) = 4 1 i ∑ a i 2 ≤ 4 N v / B i ∑ a i = 2 ( N v / B ) 2 .
The window is balanced precisely when N v / B ≤ X ≤ 7 N v / B N_v/B \le X \le7N_v/B N v / B ≤ X ≤ 7 N v / B . By Chebyshev’s inequality,
Pr [ W is balanced ] ≥ 1 − Var ( X ) ( 3 N v / B ) 2 ≥ 7 9 . \Pr[W\text{ is balanced}] \ge1-\frac{\operatorname{Var}(X)}{(3N_v/B)^2} \ge\frac{7}{9}. Pr [ W is balanced ] ≥ 1 − ( 3 N v / B ) 2 Var ( X ) ≥ 9 7 .
By linearity of expectation, the expected number of balanced windows is at least a 7 / 9 7/9 7/9 -fraction of all windows. Therefore, some labeling achieves at least this many balanced windows. The adversary chooses a labeling maximizing their number, so its deterministic choice achieves the same guarantee.
The balanced-window lemma provides many windows containing both target and buffer elements. All these elements have values in the middle half of I v I_v I v . Buffer elements that stay in their original cells can force array cost when values outside I v I_v I v are placed between them. To quantify this cost, we measure the portion of the array cost lying within a value interval. Let a 1 , … , a q a_1,\ldots,a_q a 1 , … , a q be the values currently present in the array, listed from left to right.
Definition 31. For a value interval I I I , let
V I ( A ) : = ∑ j = 1 q − 1 ∣ [ a j , a j + 1 ] ∩ I ∣ . V_I(A) := \sum_{j=1}^{q-1} \lvert[a_j,a_{j+1}] \cap I\rvert. V I ( A ) := j = 1 ∑ q − 1 ∣[ a j , a j + 1 ] ∩ I ∣ . Here, [ x , y ] [x,y] [ x , y ] denotes the interval with endpoints x x x and y y y , regardless of their order, and the absolute-value notation denotes interval length. Thus, each consecutive pair contributes the length of the portion of the interval between its values that lies in I I I .
Claim 32. For pairwise disjoint value intervals I 1 , … , I t I_1,\ldots,I_t I 1 , … , I t ,
∑ i = 1 t V I i ( A ) ≤ cost ( A ) . \sum_{i=1}^{t} V_{I_i}(A) \le\operatorname{cost}(A). i = 1 ∑ t V I i ( A ) ≤ cost ( A ) . Moreover, for every internal node v v v ,
∑ w child of v V I w ( A ) = V I v ( A ) . \sum_{w\text{ child of }v} V_{I_w}(A) = V_{I_v}(A). w child of v ∑ V I w ( A ) = V I v ( A ) .
Proof. For each consecutive pair a j , a j + 1 a_j,a_{j+1} a j , a j + 1 , the portions of [ a j , a j + 1 ] [a_j,a_{j+1}] [ a j , a j + 1 ] lying in the intervals I 1 , … , I t I_1,\ldots,I_t I 1 , … , I t are disjoint. Their total length is therefore at most ∣ a j − a j + 1 ∣ |a_j-a_{j+1}| ∣ a j − a j + 1 ∣ . Summing over all consecutive pairs proves the first assertion. The intervals of the children of v v v partition I v I_v I v . Consequently, their intersections with [ a j , a j + 1 ] [a_j,a_{j+1}] [ a j , a j + 1 ] partition its intersection with I v I_v I v . Summing their lengths over all consecutive pairs proves the equality.
We now use the balanced windows to show that, at an unpaid node, many target elements must remain unless the array has large cost within the node’s value interval. The proof uses buffer elements in their original cells to bound the cost between selected target positions.
Definition 33. Let A A A be the algorithm’s array at the end of the forward phase and I v I_v I v a visited internal interval.
U v U_v U v is the number of original elements in the target child intervals of I v I_v I v that are still present in the array (were not replaced by a value of 1 1 1 ).
M v M_v M v is the number of distinct original elements in buffer children that the algorithm has moved since the child intervals of I v I_v I v were labeled.
Note that while I v I_v I v remains unpaid, then M v < ε N v M_v < \varepsilon N_v M v < ε N v , and none of its original buffer elements has been replaced by 1. We now fix ε = 1 / 1024 \varepsilon= 1/1024 ε = 1/1024 in the definition of paid intervals. With this choice, we obtain the following lemma.
Lemma 34. Every visited unpaid interval I v I_v I v satisfies
U v ≥ δ N v or V I v ( A ) ≥ δ B ∣ I v ∣ . U_v \ge\delta N_v \qquad\text{or} \qquad V_{I_v}(A) \ge\delta B|I_v|. U v ≥ δ N v or V I v ( A ) ≥ δ B ∣ I v ∣. for some constant δ > 0 \delta> 0 δ > 0 .
Proof. Fix a visited unpaid interval I v I_v I v . Throughout the proof, an element’s original cell is the cell it occupied when I v I_v I v was first visited.
The middle B / 2 B/2 B /2 child intervals contain N v / 2 N_v/2 N v /2 elements in total. These elements are partitioned into windows of 8 N v / B 8N_v/B 8 N v / B elements each, so the number of windows is
N v / 2 8 N v / B = B 16 . \frac{N_v/2}{8N_v/B}=\frac{B}{16}. 8 N v / B N v /2 = 16 B .
By Lemma 30, the chosen labeling makes at least a 7 / 9 7/9 7/9 fraction of these windows balanced. Thus, there are at least
7 9 ⋅ B 16 = 7 B 144 \frac{7}{9}\cdot\frac{B}{16}=\frac{7B}{144} 9 7 ⋅ 16 B = 144 7 B
balanced windows. We pair consecutive balanced windows in their array order, leaving the last window unused. For B ≥ 64 B \ge64 B ≥ 64 , the bound above guarantees at least B / 64 B/64 B /64 pairs, we denote this number of pairs by r r r , which is at least 1 for B / 64 B/64 B /64 . From the first window of each pair, select N v / B N_v/B N v / B buffer elements, and from the second, select N v / B N_v/B N v / B target elements. Denote these groups, in their array order at the first visit, by
G 1 , D 1 , G 2 , D 2 , … , G r , D r . G_1,D_1,G_2,D_2,\ldots,G_r,D_r. G 1 , D 1 , G 2 , D 2 , … , G r , D r .
All selected elements have values in the middle half of I v I_v I v .
Call the original cells of the elements in D 1 , … , D r D_1,\ldots,D_r D 1 , … , D r the selected cells . There are r N v / B rN_v/B r N v / B such cells. We count them according to what has happened to the buffer groups and what currently occupies the cells. First, discard every pair whose buffer group has no unmoved element. Each discarded pair contains N v / B N_v/B N v / B distinct moved buffer elements and N v / B N_v/B N v / B selected cells. Since the buffer groups are disjoint, these pairs account for at most M v M_v M v selected cells. For each remaining pair, choose an unmoved element of G j G_j G j . It still occupies its original cell, since no buffer element has been deleted. Consider the current array segment from this fixed cell to the rightmost original cell of D j D_j D j . This segment contains all the selected cells of D j D_j D j , even though those cells need not be consecutive. Moreover, the segments share no array edge: all original cells of D j D_j D j precede all original cells of G j + 1 G_{j+1} G j + 1 .
Suppose such a segment contains a value outside I v I_v I v . Follow the consecutive array edges from the fixed buffer cell to the first value outside I v I_v I v . The value intervals of all preceding edges lie inside I v I_v I v ; the last edge contributes the distance from its inside endpoint to the boundary crossed. By the triangle inequality, their total contribution to V I I v ( A ) VI_{I_v}(A) V I I v ( A ) is at least the distance from the buffer’s value to that boundary. This distance is at least ∣ I v ∣ / 4 |I_v|/4 ∣ I v ∣/4 , because the buffer’s value lies in the middle half of I v I_v I v . Since the segments share no array edge, at most 4 V I I v ( A ) / ∣ I v ∣ 4VI_{I_v}(A)/|I_v| 4 V I I v ( A ) /∣ I v ∣ of them can contain an outside value. Each contains N v / B N_v/B N v / B selected cells, so these segments account for at most 4 N v V I I v ( A ) / ( B ∣ I v ∣ ) 4N_vVI_{I_v}(A)/(B|I_v|) 4 N v V I I v ( A ) / ( B ∣ I v ∣ ) selected cells.
Every remaining selected cell currently contains a value in I v I_v I v . The array is full, and the only newly inserted values are copies of 1, which lies outside I v I_v I v . Its occupant is therefore an original element belonging to a target or buffer child interval. A target occupant is counted by U v U_v U v . A buffer occupant must have moved: at the first visit, this cell held a target element, so the buffer element occupied a different cell. It is therefore counted by M v M_v M v . Distinct cells have distinct occupants, so there are at most U v + M v U_v+M_v U v + M v remaining selected cells.
Combining these three bounds gives
r N v B ≤ M v + 4 N v B ∣ I v ∣ V I I v ( A ) + ( U v + M v ) . \frac{rN_v}{B} \leq M_v+\frac{4N_v}{B|I_v|}VI_{I_v}(A)+(U_v+M_v). B r N v ≤ M v + B ∣ I v ∣ 4 N v V I I v ( A ) + ( U v + M v ) .
Using r ≥ B / 64 r\geq B/64 r ≥ B /64 and M v < ε N v M_v<\varepsilon N_v M v < ε N v , we obtain
U v + 4 N v B ∣ I v ∣ V I I v ( A ) ≥ ( 1 64 − 2 ε ) N v . U_v+\frac{4N_v}{B|I_v|}VI_{I_v}(A)\geq\left(\frac{1}{64}-2\varepsilon\right)N_v. U v + B ∣ I v ∣ 4 N v V I I v ( A ) ≥ ( 64 1 − 2 ε ) N v .
With our choice ε = 1 / 1024 \varepsilon=1/1024 ε = 1/1024 , this gives
U v + N v B ∣ I v ∣ V I I v ( A ) ≥ 7 N v 2048 ≥ N v 512 . U_v+\frac{N_v}{B|I_v|}VI_{I_v}(A)\geq\frac{7N_v}{2048}\geq\frac{N_v}{512}. U v + B ∣ I v ∣ N v V I I v ( A ) ≥ 2048 7 N v ≥ 512 N v .
At least one of the two terms must therefore be at least N v / 1024 N_v/1024 N v /1024 . Hence,
U v ≥ N v 1024 or V I I v ( A ) ≥ B ∣ I v ∣ 1024 . U_v\geq\frac{N_v}{1024}
\qquad\text{or}\qquad
VI_{I_v}(A)\geq\frac{B|I_v|}{1024}. U v ≥ 1024 N v or V I I v ( A ) ≥ 1024 B ∣ I v ∣ .
This proves the lemma with δ = 1 / 1024 \delta=1/1024 δ = 1/1024 .
We next bound the number of values remaining at the end of the forward phase in terms of the algorithm’s cost. Note that when terminating, the adversary may leave elements protected by buffer children of unpaired nodes. To bound this remaining population, we will use Lemma 34 .
Lemma 35 (Stopping lemma). *For a C C C -competitive algorithm, the number S S S of elements remaining at the end of the forward phase satisfies S ≤ 2 n C δ 2 B S\leq\frac{2nC}{\delta^2B} S ≤ δ 2 B 2 n C .
Proof. Let S v S_v S v be the number of original elements in I v I_v I v remaining at the end of the forward phase. Thus, S = S r o o t S = S_{\mathrm{root}} S = S root . Recall that N v = n ∣ I v ∣ N_v = n|I_v| N v = n ∣ I v ∣ and 0 < δ ≤ 1 / 2 0 < \delta\le1/2 0 < δ ≤ 1/2 . We call a child available if it is labeled as a target or released. At termination, every available child of a visited interval containing surviving original elements has been visited. Moreover, every visited leaf has no surviving original element.
We first show how to bound S v S_v S v using either the cost through I v I_v I v or the surviving populations of its available children. Suppose that I v I_v I v is unpaid. If the cost alternative of Lemma 34 holds, then
S v ≤ N v = n ∣ I v ∣ ≤ n δ B V I v ( A ) . S_v \le N_v = n|I_v| \le\frac{n}{\delta B} V_{I_v}(A). S v ≤ N v = n ∣ I v ∣ ≤ δ B n V I v ( A ) .
Otherwise, the lemma gives U v ≥ δ N v U_v \ge\delta N_v U v ≥ δ N v , and hence
S v ≤ N v ≤ U v δ = 1 δ ∑ w available child of v S w . S_v \le N_v \le\frac{U_v}{\delta} = \frac{1}{\delta} \sum_{\text{w available child of v}} S_w. S v ≤ N v ≤ δ U v = δ 1 w available child of v ∑ S w .
The equality holds because the available children of an unpaid interval are precisely its target children. Thus, when the cost is small, it suffices to bound the surviving populations in these children.
If I v I_v I v is paid, all its children are available, so
S v = ∑ w available child of v S w . S_v = \sum_{\text{w available child of v}} S_w. S v = w available child of v ∑ S w .
Combining the paid and unpaid cases, and using δ < 1 \delta< 1 δ < 1 , every visited internal interval satisfies
S v ≤ 1 δ ∑ w available child of v S w + n δ B V I v ( A ) . S_v \le\frac{1}{\delta} \sum_{\text{w available child of v}} S_w + \frac{n}{\delta B} V_{I_v}(A). S v ≤ δ 1 w available child of v ∑ S w + δ B n V I v ( A ) .
We now expand this inequality from the root down to depth d d d . Available children that have not been visited contribute zero surviving elements, so every nonzero population term can be expanded. This gives
S ≤ 1 δ d ∑ v v i s i t e d a t d e p t h d S v + n B ∑ j = 0 d − 1 1 δ j + 1 ∑ v v i s i t e d a t d e p t h j V I v ( A ) . S \le\frac{1}{\delta^d} \sum_{\substack{v\ \mathrm{visited}\\\mathrm{at\ depth}\ d}} S_v + \frac{n}{B} \sum_{j=0}^{d-1} \frac{1}{\delta^{j+1}} \sum_{\substack{v\ \mathrm{visited}\\\mathrm{at\ depth}\ j}} V_{I_v}(A). S ≤ δ d 1 v visited at depth d ∑ S v + B n j = 0 ∑ d − 1 δ j + 1 1 v visited at depth j ∑ V I v ( A ) .
The first term is zero because every visited interval at depth d d d is a leaf with no surviving original element. At each depth, the value intervals are disjoint. By Claim 32 , their cost contributions therefore sum to at most cost ( A ) ≤ C \operatorname{cost}(A) \le C cost ( A ) ≤ C . Consequently,
S ≤ n C B ∑ j = 0 d − 1 δ − ( j + 1 ) = n C B δ − d − 1 1 − δ ≤ 2 n C δ d B , S \le\frac{nC}{B} \sum_{j=0}^{d-1} \delta^{-(j+1)} = \frac{nC}{B} \frac{\delta^{-d}-1}{1-\delta} \le\frac{2nC}{\delta^d B}, S ≤ B n C j = 0 ∑ d − 1 δ − ( j + 1 ) = B n C 1 − δ δ − d − 1 ≤ δ d B 2 n C ,
where the last inequality uses δ ≤ 1 / 2 \delta\le1/2 δ ≤ 1/2 . □
Recall that C ≤ O ( n ) C \le O(n) C ≤ O ( n ) . Therefore the choice below is always possible.
Corollary 36. By choosing B ≤ n B \le n B ≤ n to be the smallest multiple of 16 satisfying B ≥ 8 C / δ d B \ge8C/\delta^d B ≥ 8 C / δ d we have
S ≤ n 4 S \le\frac{n}{4} S ≤ 4 n .
log n = d log B = O ( d log C + d 2 ) \log n = d\log B = O(d\log C + d^2) log n = d log B = O ( d log C + d 2 ) which implies that d = Ω ( log n log C + log n ) d = \Omega\left(\frac{\log n}{\log C+\sqrt{\log n}}\right) d = Ω ( l o g C + l o g n l o g n ) .
Next, we show that, at every internal depth, at least half of the original elements belong to paid nodes. Recall that N v N_v N v counts the original elements below v v v , and S S S counts those still present at the end of the forward phase. The following lemma uses the fact that unpaid nodes retain their outer buffer elements to show that paid nodes account for at least half of the original elements at each internal depth.
Claim 37. If S ≤ n / 4 S \le n/4 S ≤ n /4 , then ∑ v p a i d N v ≥ d n 2 \sum_{v\ \mathrm{paid}} N_v \ge\frac{dn}{2} ∑ v paid N v ≥ 2 d n .
Proof. Fix an internal depth ℓ ∈ { 0 , … , d − 1 } \ell\in\{0,\ldots,d-1\} ℓ ∈ { 0 , … , d − 1 } . Every node v v v at this depth that never became paid retains at least N v / 2 N_v/2 N v /2 of its original elements.
Indeed, if v v v was never visited, none of its original elements was replaced, since replacing an element below v v v requires the search to visit v v v . All N v N_v N v elements therefore remain. If v v v was visited but remains unpaid, its outer B / 2 B/2 B /2 children remain labeled as buffers. The adversary never searches these children, so their N v / 2 N_v/2 N v /2 original elements all remain.
The sets of original elements belonging to nodes at depth ℓ \ell ℓ are disjoint. Consequently,
S ≥ 1 2 ∑ v a t d e p t h ℓ v n o t p a i d N v . S \ge\frac{1}{2}\sum_{\substack{v\ \mathrm{at\ depth}\ \ell\\v\ \mathrm{not\ paid}}} N_v. S ≥ 2 1 v at depth ℓ v not paid ∑ N v .
which means that
∑ v a t d e p t h ℓ v n o t p a i d N v ≤ 2 S ≤ n 2 . \sum_{\substack{v\ \mathrm{at\ depth}\ \ell\\v\ \mathrm{not\ paid}}} N_v \le2S \le\frac{n}{2}. v at depth ℓ v not paid ∑ N v ≤ 2 S ≤ 2 n .
The nodes at this depth partition the n n n original elements. Hence,
∑ v a t d e p t h ℓ v p a i d N v = n − ∑ v a t d e p t h ℓ v n o t p a i d N v ≥ n 2 . \sum_{\substack{v\ \mathrm{at\ depth}\ \ell\\v\ \mathrm{paid}}} N_v
= n-\sum_{\substack{v\ \mathrm{at\ depth}\ \ell\\v\ \mathrm{not\ paid}}} N_v
\ge\frac{n}{2}. v at depth ℓ v paid ∑ N v = n − v at depth ℓ v not paid ∑ N v ≥ 2 n .
Summing over the d d d internal depths gives
∑ v p a i d N v ≥ d n 2 . \sum_{v\ \mathrm{paid}} N_v \ge\frac{dn}{2}. v paid ∑ N v ≥ 2 d n .
□ \square □
Each paid interval I v I_v I v requires at least ε N v \varepsilon N_v ε N v distinct buffer elements to have moved after its children were labeled. To use the preceding bound on ∑ v p a i d N v \sum_{v\ \mathrm{paid}} N_v ∑ v paid N v , we must account for possible overlap between these elements. The proof below shows that the payments can be charged without counting the same movement twice. Here, movements of the same element in different updates count separately toward recourse.
Lemma 38. In every round, the total recourse R R R during the forward phase satisfies R ≥ ε d n 2 R \ge\frac{\varepsilon dn}{2} R ≥ 2 ε d n . Consequently, repeating the rounds forces Ω ( d ) \Omega(d) Ω ( d ) amortized recourse.
Proof. For each paid node v v v , at least ⌈ ε N v ⌉ \lceil\varepsilon N_v\rceil ⌈ ε N v ⌉ distinct original buffer elements were moved after its labels were assigned and no later than the update in which it became paid. Choose ⌈ ε N v ⌉ \lceil\varepsilon N_v\rceil ⌈ ε N v ⌉ of these elements, and charge v v v to the first movement of each chosen element after its labels were assigned. We show that no movement is charged to two distinct nodes. If neither node is an ancestor of the other, their sets of original elements are disjoint, so their charges concern different elements. It remains to consider two nodes v , w v,w v , w , where v v v is an ancestor of w w w . Suppose first that v v v was still unpaid when w w w was first visited. At that time, the search could descend from v v v only through a target child. All original elements below w w w therefore belong to a target child of v v v . In particular, no element charged by w w w is a buffer element of v v v , so the two nodes cannot charge the same movement.
Suppose instead that v v v was already paid when w w w was first visited. Every movement charged to v v v occurred no later than the update in which v v v became paid. The labels at w w w were assigned after that update, and w w w counts only movements in subsequent updates. Thus, even if the two nodes charge movements of the same element, those movements occur in different updates.
Each movement consequently receives at most one charge. Since each paid node v v v receives ⌈ ε N v ⌉ \lceil\varepsilon N_v\rceil ⌈ ε N v ⌉ charges, we obtain
R ≥ ∑ v p a i d ⌈ ε N v ⌉ ≥ ε ∑ v p a i d N v ≥ ε d n 2 , R \ge\sum_{v\ \mathrm{paid}} \lceil\varepsilon N_v\rceil\ge\varepsilon\sum_{v\ \mathrm{paid}} N_v \ge\frac{\varepsilon d n}{2}, R ≥ v paid ∑ ⌈ ε N v ⌉ ≥ ε v paid ∑ N v ≥ 2 ε d n ,
where the last inequality follows from Claim 37 . □
We complete the proof of the lower bound plugging by the above lemma into Corollary 36.
Online (Insertion-Only) Sorting
In this section, we consider the online sorting problem—the insertion-only setting of the dynamic sorting problem studied in the previous section, which can also be looked at as online sorting with recourse . It is known that the best competitive ratio achievable for online sorting without recourse is Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) . Our main result is to show that the competitive ratio can be exponentially improved to O ( log n ) O(\log n) O ( log n ) using O ( 1 ) O(1) O ( 1 ) amortized recourse per element. More generally, we show the following:
Theorem 39. There are deterministic algorithms for the online sorting problem that achieve the following tradeoffs:
competitive ratio of O ( R ⋅ log 1 / R n ) O\left(R\cdot\log^{1/R}n\right) O ( R ⋅ log 1/ R n ) with recourse R ∈ [ O ( 1 ) , O ( log log n ) ] R\in[O(1),O(\log\log n)] R ∈ [ O ( 1 ) , O ( log log n )] , and
competitive ratio of C ∈ [ O ( 1 ) , O ( log log n ) ] C\in[O(1),O(\log\log n)] C ∈ [ O ( 1 ) , O ( log log n )] with recourse O ( C ⋅ log 1 / C n ) O\left(C\cdot\log^{1/C}n\right) O ( C ⋅ log 1/ C n ) .
Remark. Our result assumes, as done in many papers on this topic, that the optimal cost of the complete insertion sequence is known to the algorithm. For example, this holds when all values lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] and both 0 and 1 appear in the sequence, so that O P T = 1 OPT=1 O P T = 1 . This assumption is required by the algorithm of Azar et al. [4 ] , which we use as a subroutine.
The tradeoff achieved by the above theorem is shown in Figure 10 . In particular, we get the following bounds:
Figure 10. The tradeoff between competitive ratio and recourse achieved by Theorem 39.
The two tradeoffs in Theorem 39 are achieved by two different data structures:
Low-Recourse Block Gadget (LRBG): This data structure takes as input a sequence of k k k sorted blocks of possibly unequal size, and returns an array of cost O ( b ⋅ log b k ) O(b \cdot\log_b k) O ( b ⋅ log b k ) using O ( log b k ) O(\log_b k) O ( log b k ) recourse per element, for some parameter b b b . We describe this gadget in § 7.1 .
High Recourse Block Gadget (HRBG): Similar to LRBG, this data structure takes as input a sequence of k k k sorted blocks of possibly unequal size. However, it uses more recourse to achieve a lower cost bound than LRBG: namely, it returns an array of cost O ( log b k ) O(\log_b k) O ( log b k ) using O ( b ⋅ log b k ) O(b \cdot\log_b k) O ( b ⋅ log b k ) recourse per element, for some parameter b b b . We describe this gadget in § 7.2 .
The LRBG and HRBG data structures operate on sorted blocks. To create these blocks from a sequence of inserted elements, we use a data structure from prior work of Azar, Panigrahi, and Vardi [4 ] . The APV data structure (see § 6 in [4 ] ) has the following property: for any β ∈ [ O ( log n ) , O ( log 2 n ) ] \beta\in[O(\log n), O(\log^2 n)] β ∈ [ O ( log n ) , O ( log 2 n )] , given an input sequence comprising n n n elements, it inserts the elements in an array of size O ( β n log n ) O(\beta n \log n) O ( β n log n ) such that the sum of absolute differences between elements in consecutive non-empty array locations is at most O ( log n β ) O\left(\frac{\log n}{\beta}\right) O ( β l o g n ) . The data structure does not use any recourse.
We use the APV gadget in multiple iterations on input sequences of various lengths in our data structure. For an input sequence of length r r r , we set β : = O ( log r ) \beta:= O(\log r) β := O ( log r ) . Furthermore, at the end of inserting r r r elements, we re-sort these elements and make the array compact by inserting them in contiguous locations. This last step has overall recourse of O ( r ) O(r) O ( r ) , i.e., O ( 1 ) O(1) O ( 1 ) recourse per element. Therefore, we have the following claim:
Claim 40. Given a sequence of r r r elements and an empty array of size O ( r log 2 r ) O(r\log^2 r) O ( r log 2 r ) , the APV algorithm can be used to sort the elements and return them in a contiguous sorted block of size r r r , while incurring O ( 1 ) O(1) O ( 1 ) recourse per element. At any intermediate stage of this process, the cost of the elements is at most O ( 1 ) O(1) O ( 1 ) .
We now describe the use of Claim 40 to create sorted blocks that are input to the LRBG and HRBG gadgets. The overall algorithm comprises a set of phases that process geometrically decreasing numbers of elements. In other words, the i i i th phase inserts n i : = n / 2 i n_i := n/2^i n i := n / 2 i elements. We further subdivide a phase comprising n i n_i n i elements into t = O ( log 2 n ) t = O(\log^2 n) t = O ( log 2 n ) subphases, each of which inserts n i / t n_i/t n i / t elements. Each subphase is a separate invocation of the APV gadget with r : = n i / t r := n_i/t r := n i / t . Note that in such a subphase, the array has contiguous empty space of size at least n i = ( n i / t ) ⋅ t = Ω ( r log 2 r ) n_i = (n_i/t)\cdot t = \Omega(r\log^2 r) n i = ( n i / t ) ⋅ t = Ω ( r log 2 r ) , which satisfies the condition of Claim 40. Therefore, the APV gadget returns the elements in a subphase in sorted order, incurring O ( 1 ) O(1) O ( 1 ) recourse per element and at most O ( 1 ) O(1) O ( 1 ) cost at any intermediate stage.
We summarize the use of the APV algorithm below:
Claim 41. The invocations of the APV algorithm produce a sequence of O ( log 3 n ) O(\log^{3} n) O ( log 3 n ) sorted blocks (of unequal size), have cost at most O ( 1 ) O(1) O ( 1 ) at any intermediate stage within a block, and incur O ( 1 ) O(1) O ( 1 ) amortized recourse per element.
Low Recourse Block Gadget
We now describe the Low Recourse Block Gadget (with parameter b b b ). It is convenient to first consider the special case where each sorted block is just a single element. In this case, the LRBG data structure is defined via a virtual tree of arity b b b with k k k leaves that are identified with the k k k array cells. The insertion algorithm is simple: the arriving element is inserted in the first empty cell in the array. There is only one additional operation to maintain the data structure: when all the leaves in any subtree of the virtual tree are full, the corresponding subarray is sorted at O ( 1 ) O(1) O ( 1 ) recourse per element.
To extend this data structure to sorted input blocks, we make a simple modification: each leaf in the virtual tree is no longer associated with a single array cell, but the i i i th leaf is associated with a subarray of size equal to the i i i th sorted block inserted into the data structure. The re-sorting steps are exactly as earlier, i.e., when all the leaves in a subtree are full, we sort all the elements in the corresponding subarrays at O ( 1 ) O(1) O ( 1 ) recourse per element.
We give an illustration of the LRBG data structure in Figure 11 .
Figure 11. Low Recourse Block Gadget (LRBG) for arity b b b , illustrated with b = 3 b = 3 b = 3 . Each leaf of the virtual tree is associated with one sorted block B i B_i B i . The blue boxes show the nested subtrees containing a particular block, here B 5 B_5 B 5 : the leaf subtree, its parent subtree, and the root subtree. Whenever such a subtree becomes full, the corresponding contiguous interval of blocks is re-sorted.
Lemma 42. The Low Recourse Block Gadget with parameter b b b inserts a sequence of k k k sorted blocks (of arbitrary sizes) with O ( b ⋅ log b k ) O(b \cdot\log_b k) O ( b ⋅ log b k ) cost and O ( log b k ) O(\log_b k) O ( log b k ) amortized recourse per element.
Proof. For the recourse bound, note that every element participates in at most O ( log b k ) O(\log_b k) O ( log b k ) re-sorts, i.e., once for a subtree of each height. For the cost bound, call a subtree of the virtual tree active if its leaves are already full, but not all leaves in its parent subtree are full yet. Note that there are at most b − 1 b - 1 b − 1 active subtrees at every height at any time. Moreover, the elements in any active subtree are sorted. Therefore, the total cost is at most ( b − 1 ) ⋅ O ( log b k ) = O ( b ⋅ log b k ) (b - 1) \cdot O(\log_b k) = O(b \cdot\log_b k) ( b − 1 ) ⋅ O ( log b k ) = O ( b ⋅ log b k ) .
High Recourse Block Gadget
We now describe the High Recourse Block Gadget (with parameter b b b ). As in the case of LRBG, it will be convenient to first consider the special case of singleton input blocks. The data structure uses a parameter L = O ( log b k ) L = O(\log_b k) L = O ( log b k ) to denote the number of levels. At any time, the elements inserted so far are organized into a set of sorted super-blocks that are contiguous from left to right in the array. There is exactly one super-block at each level ℓ ∈ { L , L − 1 , … , 0 } \ell\in\{L, L-1, \ldots, 0\} ℓ ∈ { L , L − 1 , … , 0 } and these super-blocks are organized in decreasing order of levels from left to right in the array. We say that the super-block at level ℓ + 1 \ell+1 ℓ + 1 is the parent of the super-block at level ℓ \ell ℓ . The size of the super-block at level ℓ \ell ℓ is not fixed: it can vary from being empty, i.e., size 0, to having a maximum size of k ℓ / L k^{\ell/L} k ℓ / L . A super-block that is at its maximum size is said to be full . Eventually, the super-block at level L L L is full and all other super-blocks are empty, i.e., the entire array of size k k k is sorted.
The super-blocks are maintained using the following insertion subroutine. The incoming element is always inserted in the super-block at level 0. Note that this super-block can hold at most 1 element. By the subsequent operations that we will describe, this super-block will always be empty once we have completed the insertion of an element and are ready to insert the next element. Therefore, it is always feasible to insert the new element in this super-block. We have just one additional maintenance operation: whenever a super-block becomes full, we move the elements in the super-block to its parent super-block and re-sort all the elements in the parent super-block at O ( 1 ) O(1) O ( 1 ) recourse per element of the parent super-block. Note that these operations can cascade, i.e., we merge elements in the super-block at level ℓ \ell ℓ into the super-block at level ℓ + 1 \ell+1 ℓ + 1 , which makes it full and has to be merged into the super-block at level ℓ + 2 \ell+2 ℓ + 2 , and so on. After merging the elements of a super-block into its parent, the super-block itself becomes empty. Therefore, the super-block at level 0, which can only hold 1 element, immediately becomes full on inserting a new element, gets merged into the super-block at level 1 thereby becoming empty, and is ready to accept the next incoming element.
To extend this data structure to an insertion sequence comprising k k k sorted blocks, we make only one change: the super-block at level ℓ \ell ℓ can now accept at most k ℓ / L k^{\ell/L} k ℓ / L sorted input blocks rather than k ℓ / L k^{\ell/L} k ℓ / L elements. Extending this idea, the super-block becomes full once it has accepted k ℓ / L k^{\ell/L} k ℓ / L sorted input blocks rather than k ℓ / L k^{\ell/L} k ℓ / L elements. As earlier, once it becomes full, all its elements are merged into its parent super-block at level ℓ + 1 \ell+1 ℓ + 1 at O ( 1 ) O(1) O ( 1 ) recourse per element of the parent super-block. As earlier, after the merger, the super-block at level ℓ \ell ℓ becomes empty. This means that the maximum size of a super-block is no longer fixed, but this does not affect the operation of our data structure.
We give an illustration of the HRBG data structure in Figure 12 .
Figure 12. High Recourse Block Gadget (HRBG). The array consists of sorted super-blocks arranged from left to right in decreasing level order. The capacity of level ℓ \ell ℓ is k ℓ / L k^{\ell/L} k ℓ / L . A new item is inserted into S 0 S_0 S 0 . Whenever a super-block becomes full, its contents are merged into its parent, the parent is re-sorted, and the super-block becomes empty.
Lemma 43. The High Recourse Block Gadget with parameter b b b inserts a sequence of k k k sorted blocks (of arbitrary sizes) with O ( log b k ) O(\log_b k) O ( log b k ) cost and O ( b ⋅ log b k ) O(b \cdot\log_b k) O ( b ⋅ log b k ) amortized recourse per element.
Proof. Since the algorithm maintains L + 1 = O ( log b k ) L + 1 = O(\log_b k) L + 1 = O ( log b k ) sorted super-blocks at any stage (some of these can be empty), the cost is at most O ( log b k ) O(\log_b k) O ( log b k ) . To bound recourse, note that an element participates in a re-sort operation at any level ℓ + 1 \ell+ 1 ℓ + 1 every time the super-block at level ℓ \ell ℓ becomes full. This can happen at most k 1 / L k^{1/L} k 1/ L times, after which the super-block at level ℓ + 1 \ell+ 1 ℓ + 1 will be full and the element will move to the super-block at level ℓ + 2 \ell+ 2 ℓ + 2 . Therefore, each element participates in at most ( L + 1 ) ⋅ k 1 / L = O ( b ⋅ log b k ) (L + 1) \cdot k^{1/L} = O(b \cdot\log_b k) ( L + 1 ) ⋅ k 1/ L = O ( b ⋅ log b k ) re-sort operations, and incurs ( L + 1 ) ⋅ k 1 / L = O ( b ⋅ log b k ) (L + 1) \cdot k^{1/L} = O(b \cdot\log_b k) ( L + 1 ) ⋅ k 1/ L = O ( b ⋅ log b k ) amortized recourse.
Putting it Together
Proof of Theorem 39 . Our overall algorithm uses the sequence of sorted blocks produced by APV (Claim 41 ) as input to either LRBG or HRBG, i.e., k = O ( log 3 n ) k = O(\log^3 n) k = O ( log 3 n ) . For LRBG, we set log b k = 3 R \log_b k = 3R log b k = 3 R , i.e., b = k 1 / ( 3 R ) = O ( log 1 / R n ) b = k^{1/(3R)} = O(\log^{1/R} n) b = k 1/ ( 3 R ) = O ( log 1/ R n ) , in Lemma 42 to obtain the first tradeoff in Theorem 39 , with O ( R ) O(R) O ( R ) amortized recourse. For HRBG, we similarly set log b k = 3 C \log_b k = 3C log b k = 3 C , i.e., b = k 1 / ( 3 C ) = O ( log 1 / C n ) b = k^{1/(3C)} = O(\log^{1/C} n) b = k 1/ ( 3 C ) = O ( log 1/ C n ) , in Lemma 43 to obtain the second tradeoff in Theorem 39 , with O ( C ) O(C) O ( C ) competitiveness. These tradeoffs include the O ( 1 ) O(1) O ( 1 ) cost and O ( 1 ) O(1) O ( 1 ) amortized recourse per element due to APV as given in Claim 41 .
Online and Dynamic Sorting with ( 1 + ε ) n (1 + \varepsilon)n ( 1 + ε ) n -Space
In this section, we show that if the array has extra space, i.e., if the array is of size m = ( 1 + ε ) n m = (1 + \varepsilon)n m = ( 1 + ε ) n for any fixed ε > 0 \varepsilon> 0 ε > 0 , and there are at most n n n elements stored in it at any time, then the online and dynamic sorting problems are equivalent:
Claim 44. Suppose there is a (deterministic) algorithm for online sorting that inserts a sequence of n n n elements in an array of size n n n with cost c c c and amortized recourse r r r per element. Then, for any ε > 0 \varepsilon> 0 ε > 0 , there is a (deterministic) algorithm for dynamic sorting that maintains at most n n n elements in an array of size ( 1 + ε ) n (1 + \varepsilon)n ( 1 + ε ) n with cost 2 c + 1 2c + 1 2 c + 1 and amortized recourse r + O ( 1 / ε ) r + O(1/\varepsilon) r + O ( 1/ ε ) per element.
Remark. We assume, as before, that the minimum and maximum values are represented by two permanent elements that cannot be deleted. In particular, we may assume that all values lie in [ 0 , 1 ] [0, 1] [ 0 , 1 ] and that 0 0 0 and 1 1 1 remain present throughout the execution.
Proof. The dynamic sorting algorithm re-sorts the elements after every ε n \varepsilon n ε n steps (element insertions or deletions), and compacts them in the array leaving an empty subarray of size ε n \varepsilon n ε n . Between any two re-sorts, element insertions execute the online sorting algorithm on the empty subarray of size ε n \varepsilon n ε n . This is valid because there can be at most ε n \varepsilon n ε n insertions between two re-sorts. All element deletions are postponed to the next re-sort, at which time the deleted elements are not included in the sorted array. In other words, although an element is actually removed from the array on deletion, the online sorting algorithm (which cannot handle element deletions) continues assuming that the deleted element is still in the array.
The algorithm has a cost of c c c on the part of the array where elements are being inserted, and a cost of 1 1 1 between the previously re-sorted subarray and this subarray where insertions are being made. For the recourse bound, note that the only additional recourse is O ( n ) O(n) O ( n ) for every re-sort, which can be charged to the ε n \varepsilon n ε n steps between every two consecutive re-sorts.
Using Claim 44 and Theorem 39 , we get:
Theorem 45. For any ε > 0 \varepsilon> 0 ε > 0 , there are deterministic algorithms for dynamic sorting that maintain at most n n n elements in an array of size ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n with the following tradeoffs:
competitive ratio of O ( R ⋅ log 1 / R n ) O\left(R \cdot\log^{1/R} n\right) O ( R ⋅ log 1/ R n ) with recourse R + O ( 1 / ε ) R + O(1/\varepsilon) R + O ( 1/ ε ) , where R ∈ [ O ( 1 ) , O ( log log n ) ] R \in[O(1), O(\log\log n)] R ∈ [ O ( 1 ) , O ( log log n )] , and
competitive ratio of C ∈ [ O ( 1 ) , O ( log log n ) ] C \in[O(1), O(\log\log n)] C ∈ [ O ( 1 ) , O ( log log n )] with recourse O ( C ⋅ log 1 / C n + 1 / ε ) O(C \cdot\log^{1/C} n + 1/\varepsilon) O ( C ⋅ log 1/ C n + 1/ ε ) .
In particular, this implies that we can match the tradeoffs listed after Theorem 39 —O ( log n ) O(\log n) O ( log n ) -competitiveness with O ( 1 ) O(1) O ( 1 ) recourse, O ( log log n ) O(\log\log n) O ( log log n ) -competitiveness with O ( log log n ) O(\log\log n) O ( log log n ) recourse, and O ( 1 ) O(1) O ( 1 ) -competitiveness with O ( log n ) O(\log n) O ( log n ) recourse—even in the fully-dynamic setting, provided the array is of size ( 1 + ε ) n (1+\varepsilon)n ( 1 + ε ) n . This represents a substantial improvement in the competitive ratio over the best-known bound without recourse even in the insertion-only setting, that of O ( log 2 n ε ) O\left(\frac{\log^2 n}{\varepsilon}\right) O ( ε l o g 2 n ) obtained by [4 ] .
Closing Remarks
In this paper, we studied online sorting with recourse, focusing on the fully dynamic setting where elements may be inserted and deleted without additional space. Our main result is a deterministic algorithm that achieves an O ( log 2 n ) O(\log^2 n) O ( log 2 n ) competitive ratio with O ( log 4 n ) O(\log^4 n) O ( log 4 n ) amortized recourse per update. The main ingredient is a recursive data structure that allows limited disorder to support efficient updates. We also complement this upper bound with a lower bound showing that for deterministic algorithms, the recourse bound cannot be improved beyond the exact exponent in the poly-logarithmic factor. Our results for insertion-only sorting and fully dynamic sorting with additional space provide stronger tradeoffs, thereby showing that these problems are strictly easier than the full-dynamic problem.
Several questions remain open. Most importantly, we would like to understand the optimal tradeoff between competitiveness and recourse when the array has exactly n n n cells. In particular, can we obtain an O ( 1 ) O(1) O ( 1 ) competitive ratio with poly-logarithmic amortized recourse? Our lower bound shows that O ( 1 ) O(1) O ( 1 ) -competitiveness requires Ω ( log n ) \Omega(\sqrt{\log n}) Ω ( log n ) amortized recourse for deterministic algorithms, but considerable gaps remain between the known upper and lower bounds.
Another direction is to obtain worst-case rather than amortized recourse guarantees. Our algorithm relies on rebuilding operations that may move many elements in a single update, and it is unclear whether these operations can be distributed over time without additional space or a significant loss in competitiveness. Finally, it would be interesting to extend our techniques to fully dynamic online metric TSP [ABB⁺24, Ber25, APV26b]. Our construction relies heavily on linear ordering of the elements, and understanding which of its ideas extend to general metrics remains an interesting challenge.
AI Methodology
We used ChatGPT to generate figures (some of which were subsequently edited), assist with proof checking, and improve the writing and presentation of the paper. In terms of the results themselves, the proof of the fully dynamic lower bound was developed through multiple rounds of interaction with ChatGPT. The remaining results and underlying proof arguments were developed by the authors. The authors take full responsibility for the correctness and contents of the paper.
Omitted Proof from Section 2
Proof of Lemma 5. Write S = ( x 1 , … , x k ) S=(x_1,\ldots,x_k) S = ( x 1 , … , x k ) and S ′ = ( x p 1 , … , x p m ) S'=(x_{p_1},\ldots,x_{p_m}) S ′ = ( x p 1 , … , x p m ) , where p 1 < ⋯ < p m p_1<\cdots<p_m p 1 < ⋯ < p m . Fix a threshold z z z , and let b j = 1 [ x j > z ] b_j=1[x_j>z] b j = 1 [ x j > z ] . For every pair of consecutive elements in S ′ S' S ′ ,
∣ b p r + 1 − b p r ∣ ≤ ∑ j = p r p r + 1 − 1 ∣ b j + 1 − b j ∣ . \lvert b_{p_{r+1}}-b_{p_r}\rvert\le\sum_{j=p_r}^{p_{r+1}-1}\lvert b_{j+1}-b_j\rvert. ∣ b p r + 1 − b p r ∣ ≤ j = p r ∑ p r + 1 − 1 ∣ b j + 1 − b j ∣ .
Since these index ranges are disjoint, summing over r = 1 , … , m − 1 r=1,\ldots,m-1 r = 1 , … , m − 1 gives
cross z ( S ′ ) ≤ ∑ j = 1 k − 1 ∣ b j + 1 − b j ∣ = cross z ( S ) . \operatorname{cross}_z(S')\le\sum_{j=1}^{k-1}\lvert b_{j+1}-b_j\rvert=\operatorname{cross}_z(S). cross z ( S ′ ) ≤ j = 1 ∑ k − 1 ∣ b j + 1 − b j ∣ = cross z ( S ) .
Now suppose cross z ( S ) ≤ C \operatorname{cross}_z(S)\le C cross z ( S ) ≤ C for every z z z . By (1),
cost ( S ′ ) = ∫ min S ′ max S ′ cross z ( S ′ ) d z ≤ C ( max S ′ − min S ′ ) = C ⋅ OPT ( S ′ ) . \operatorname{cost}(S')=\int_{\min S'}^{\max S'}\operatorname{cross}_z(S')\,dz\le C(\max S'-\min S')=C\cdot\operatorname{OPT}(S'). cost ( S ′ ) = ∫ m i n S ′ m a x S ′ cross z ( S ′ ) d z ≤ C ( max S ′ − min S ′ ) = C ⋅ OPT ( S ′ ) .
For sequences of at most one element, the conclusion holds trivially.
Omitted Proofs from Section 4
Proof of Claim 6. We prove the claim by induction on i i i . For i = 1 i=1 i = 1 , the DST is a sorted array, so the claim is immediate. Suppose i > 1 i>1 i > 1 . If the DST consists of a single block with original section O O O , the claim follows directly from the induction hypothesis applied to O O O . Otherwise, write
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . S=O_1\mid T_2\mid O_2\mid O_3. S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 .
By the Block Ordering invariant,
O 1 < O 2 < T 2 , O 2 < O 3 . O_1<O_2<T_2,\qquad O_2<O_3. O 1 < O 2 < T 2 , O 2 < O 3 .
Thus, every element of O 1 O_1 O 1 is smaller than every element outside O 1 O_1 O 1 , so the minimum of S S S lies in O 1 O_1 O 1 . Since O 1 O_1 O 1 is an ( i − 1 ) (i-1) ( i − 1 ) -level DST, the induction hypothesis implies that its minimum occupies its leftmost cell, which is also the leftmost cell of S S S . This completes the induction.
Proof of Claim 7. We prove the claim by induction on i i i . For i = 1 i=1 i = 1 , the DST is a sorted array, so the claim is immediate. Suppose i > 1 i>1 i > 1 . If the DST consists of a single block with original section O O O , the claim follows directly from the induction hypothesis applied to O O O . Otherwise, write
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . S=O_1\mid T_2\mid O_2\mid O_3. S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 .
By the Block Ordering invariant,
O 1 < O 2 < T 2 , O 2 < O 3 . O_1<O_2<T_2,\qquad O_2<O_3. O 1 < O 2 < T 2 , O 2 < O 3 .
Thus, every element of O 1 O_1 O 1 and O 2 O_2 O 2 is smaller than every element of O 3 O_3 O 3 . It remains to consider T 2 T_2 T 2 . If O 3 O_3 O 3 is a level-1 section, the ordering invariant gives T 2 < O 3 T_2 < O_3 T 2 < O 3 . Otherwise, by the Block Sizes invariant, O 3 O_3 O 3 consists of three blocks. Writing
O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ , O_3 = O'_1 \mid T'_2 \mid O'_2 \mid O'_3, O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ ,
the ordering invariant gives T 2 < O 2 ′ T_2 < O'_2 T 2 < O 2 ′ . Since O 2 ′ O'_2 O 2 ′ is nonempty, the maximum element of S S S must belong to O 3 O_3 O 3 .
By the induction hypothesis, the maximum of O 3 O_3 O 3 occupies its rightmost cell, which is also the rightmost cell of S S S . This completes the induction.
Proof of Lemma 8. We prove the crossing bound by induction on i i i .
For i = 1 i = 1 i = 1 , the DST is a sorted array and therefore crosses any threshold at most once. Suppose i > 1 i > 1 i > 1 . If S S S consists of a single block, the claim follows from the induction hypothesis. Otherwise, write
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . S = O_1 \mid T_2 \mid O_2 \mid O_3. S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 .
Fix a threshold z z z . We first bound the crossings within the four sections, and then account for the crossings between them.
Since O 1 < O 2 < O 3 O_1 < O_2 < O_3 O 1 < O 2 < O 3 , at most one of these three original sections can contain elements on both sides of z z z . Thus, if T 2 T_2 T 2 does not cross z z z , the induction hypothesis bounds the total number of crossings within the sections by 4 ( i − 1 ) 4(i - 1) 4 ( i − 1 ) .
Suppose instead that T 2 T_2 T 2 crosses z z z . Since O 1 < O 2 < T 2 O_1 < O_2 < T_2 O 1 < O 2 < T 2 , both O 1 O_1 O 1 and O 2 O_2 O 2 lie entirely below z z z . The block ordering invariant also ensures that O 3 O_3 O 3 crosses z z z at most once.
Indeed, if O 3 O_3 O 3 is a level-1 section, then T 2 < O 3 T_2 < O_3 T 2 < O 3 , so all its elements lie above z z z . Otherwise, writing
O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ , O_3 = O'_1 \mid T'_2 \mid O'_2 \mid O'_3, O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ ,
the terminal ordering gives
O 1 ′ < T 2 < ( T 2 ′ ∪ O 2 ′ ∪ O 3 ′ ) . O'_1 < T_2 < (T'_2 \cup O'_2 \cup O'_3). O 1 ′ < T 2 < ( T 2 ′ ∪ O 2 ′ ∪ O 3 ′ ) .
Hence O 3 O_3 O 3 consists of a prefix below z z z followed by a suffix above z z z , and therefore crosses z z z at most once.
In either case, the total number of crossings within the four sections is at most 4 ( i − 1 ) + 1 4(i - 1) + 1 4 ( i − 1 ) + 1 . Finally, there are at most three boundaries between consecutive sections, each contributing at most one additional crossing. Therefore,
cross z ( S ) ≤ 4 ( i − 1 ) + 1 + 3 = 4 i . \operatorname{cross}_z(S) \le4(i - 1) + 1 + 3 = 4i. cross z ( S ) ≤ 4 ( i − 1 ) + 1 + 3 = 4 i .
If all elements lie in an interval I I I , no threshold outside I I I is crossed. Integrating the bound using (1) gives
cost ( S ) = ∫ I cross z ( S ) d z ≤ 4 i ∣ I ∣ . \operatorname{cost}(S) = \int_I \operatorname{cross}_z(S)\, \mathrm{d}z \le4i|I|. cost ( S ) = ∫ I cross z ( S ) d z ≤ 4 i ∣ I ∣.
Proof of Claim 9. Let D D D be the DST on which InsertMax is invoked. The operation fills its last cell with an element y y y larger than every element already stored in D D D . This cell is also the last cell of every DST along the chain of last original sections of D D D . Since y y y is larger than all elements in these sections, by Claim 7, the insertion is consistent with the position of the maximum element at every recursive level.
We verify each invariant separately.
Block Ordering. The new element is inserted along the chain of last original sections. At each three-block level, it is added to O 3 O_3 O 3 , and since y y y is larger than every existing element, the ordering O 2 < O 3 O_2 < O_3 O 2 < O 3 remains valid.
All other ordering constraints involve sections whose stored elements are unchanged, or require elements of the last original section to be larger than those of a preceding section. These constraints are therefore preserved as well.
Thus, InsertMax preserves all structural invariants within D D D .
Proof of Claim 10. The operation InsertMax only places y y y in the existing hole, without moving any other element. Thus, its recourse is at most one.
Proof of Claim 11. We prove the claim by induction on the level of the rebuilt section. For a level-1 section, ReBuild produces a sorted array, so all invariants hold.
Consider a level-( i + 1 ) (i+1) ( i + 1 ) section D D D , where i ≥ 1 i \ge1 i ≥ 1 .
Block Sizes. We first establish the size bound needed for rebuilding. Since higher-level size violations are handled first, the block containing D D D satisfies its size bound. This block belongs to a level-( i + 2 ) (i+2) ( i + 2 ) section, so its size is at most 12 ⋅ 2 i + 1 − 1 12 \cdot2^{i+1} - 1 12 ⋅ 2 i + 1 − 1 . Consequently,
∣ D ∣ ≤ 24 ⋅ 2 i − 1 ≤ 25 ⋅ 2 i − 2. |D| \le24 \cdot2^i - 1 \le25 \cdot2^i - 2. ∣ D ∣ ≤ 24 ⋅ 2 i − 1 ≤ 25 ⋅ 2 i − 2.
We now verify that rebuilding produces valid block sizes, distinguishing the two rebuilding cases.
Repartition. If ∣ D ∣ ≤ 11 ⋅ 2 i |D| \le11 \cdot2^i ∣ D ∣ ≤ 11 ⋅ 2 i , we construct a single block, whose original section contains fewer than 12 ⋅ 2 i 12 \cdot2^i 12 ⋅ 2 i cells.
Otherwise, we construct three blocks. The middle block contains exactly 2 i 2^i 2 i cells, while the last and first blocks contain
L = max { 8 ⋅ 2 i , ⌈ ∣ D ∣ − 2 i 2 ⌉ } , F = ∣ D ∣ − 2 i − L L = \max\left\{8 \cdot2^i,\left\lceil\frac{|D|-2^i}{2}\right\rceil\right\}, \qquad F = |D|-2^i-L L = max { 8 ⋅ 2 i , ⌈ 2 ∣ D ∣ − 2 i ⌉ } , F = ∣ D ∣ − 2 i − L
cells, respectively.
Since 11 ⋅ 2 i < ∣ D ∣ ≤ 25 ⋅ 2 i − 2 11 \cdot2^i < |D| \le25 \cdot2^i - 2 11 ⋅ 2 i < ∣ D ∣ ≤ 25 ⋅ 2 i − 2 , these sizes satisfy
2 i + 1 ≤ F < 12 ⋅ 2 i , 8 ⋅ 2 i ≤ L < 12 ⋅ 2 i . 2^{i+1} \le F < 12 \cdot2^i, \qquad8 \cdot2^i \le L < 12 \cdot2^i. 2 i + 1 ≤ F < 12 ⋅ 2 i , 8 ⋅ 2 i ≤ L < 12 ⋅ 2 i .
Hence all three blocks satisfy their required size bounds.
Cleanup. In this case, the existing three block sizes are preserved. They already satisfy their bounds, since repartition takes precedence whenever a size violation occurs.
In both cases, every recursive level-i i i section contains fewer than 12 ⋅ 2 i 12 \cdot2^i 12 ⋅ 2 i cells. Since
12 ⋅ 2 i − 1 ≤ 25 ⋅ 2 i − 1 − 2 , 12 \cdot2^i - 1 \le25 \cdot2^{i-1} - 2, 12 ⋅ 2 i − 1 ≤ 25 ⋅ 2 i − 1 − 2 ,
the same capacity bound holds at the next recursive level. The block-size invariants of these sections therefore follow by induction.
Block Ordering. The stored elements are sorted before being distributed among the new original sections. Consequently, the original sections are ordered by value. Since all transfer sections are empty, every ordering constraint involving a transfer section within D D D holds trivially. The recursive ordering invariants follow from the induction hypothesis.
Finally, rebuilding preserves the total number of cells and, if a hole is present, keeps it at the last position of D D D . The hole is included in the block-size calculations and does not affect the ordering of stored elements.
Hence all internal structural invariants of the rebuilt section are satisfied.
Proof of Claim 12. For i = 1 i = 1 i = 1 , the section contains at most 24 cells, so rebuilding incurs O ( 1 ) O(1) O ( 1 ) recourse. For i > 1 i > 1 i > 1 , the capacity condition guarantees that the section contains O ( 2 i ) O(2^i) O ( 2 i ) cells. Since ReBuild sorts and rebuilds the entire section, moving each stored element at most once, its recourse is at most the number of stored elements, which is O ( 2 i ) O(2^i) O ( 2 i ) .
Proof of Claim 13. The SwapHole operation transfers an empty cell between the original and transfer sections of a middle block. We verify the four structural invariants separately.
We examine the affected sections from highest level to lowest. Whenever a section requires repair, we rebuild either that section or its three-block parent, according to the rules of SwapHole.
In the latter case, the parent was examined first and already satisfies its size bounds. Thus, ReBuild preserves its top-level block sizes. In either case, Claim 11 guarantees that rebuilding restores the required size bounds within the rebuilt section.
Repeating this procedure restores the Block Sizes invariant throughout the DST.
Block Ordering. The boundary change does not move any stored element, so all ordering constraints remain satisfied. By Claim 11, rebuilding also restores the ordering constraints within the rebuilt section.
The only difficulty arises when a section S ′ S' S ′ requiring repair is the last original section of a three-block section
S = O 1 ∣ T 2 ∣ O 2 ∣ S ′ . S = O_1 \mid T_2 \mid O_2 \mid S'. S = O 1 ∣ T 2 ∣ O 2 ∣ S ′ .
Rebuilding S ′ S' S ′ may change the elements in its first original section, potentially violating their ordering with T 2 T_2 T 2 .
To avoid this, we rebuild S S S instead. This empties T 2 T_2 T 2 , eliminating the affected ordering constraint.
We must also verify that rebuilding S S S preserves ordering constraints at higher levels. Suppose S S S is itself the last original section of a higher-level three-block section
S ^ = O ^ 1 ∣ T ^ 2 ∣ O ^ 2 ∣ S . \widehat{S} = \widehat{O}_1 \mid\widehat{T}_2 \mid\widehat{O}_2 \mid S. S = O 1 ∣ T 2 ∣ O 2 ∣ S .
When T ^ 2 \widehat{T}_2 T 2 is nonempty, the Block Ordering invariant requires
O 1 < T ^ 2 < ( T 2 ∪ O 2 ∪ S ′ ) . O_1 < \widehat{T}_2 < (T_2 \cup O_2 \cup S'). O 1 < T 2 < ( T 2 ∪ O 2 ∪ S ′ ) .
Hence, it suffices to show that rebuilding S S S preserves the elements belonging to O 1 O_1 O 1 .
Since S S S was examined before S ′ S' S ′ , its middle original section O 2 O_2 O 2 is nonempty. Moreover, the hole is in S ′ S' S ′ or outside S S S , so neither O 1 O_1 O 1 nor O 2 O_2 O 2 contains the hole. By the Block Ordering invariant,
O 1 < O 2 , O 2 < T 2 , O 2 < S ′ . O_1 < O_2,\qquad O_2 < T_2,\qquad O_2 < S'. O 1 < O 2 , O 2 < T 2 , O 2 < S ′ .
Thus, O 1 O_1 O 1 contains precisely the smallest ∣ O 1 ∣ |O_1| ∣ O 1 ∣ elements of S S S .
Since the block sizes of S S S are preserved during rebuilding, its first original section retains the same elements. Consequently, the ordering constraint involving T ^ 2 \widehat{T}_2 T 2 remains satisfied.
Thus, rebuilding S S S eliminates the ordering constraint involving T 2 T_2 T 2 without violating any ordering constraints at higher levels.
Therefore, all four structural invariants are preserved. □
Proof of Claim 14. We prove the claim by induction on i i i . Consider an i i i -level DST
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 , S = O_1 \mid T_2 \mid O_2 \mid O_3, S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 ,
with a hole at the end of T 2 T_2 T 2 .
We verify each structural invariant separately.
Number and Structure of Blocks. Moving an element into the hole does not change the ownership of any cell. If O 3 O_3 O 3 is a level-1 section, the operation also leaves the recursive structure unchanged.
Otherwise, the only change in cell ownership is performed by SwapHole ( O 2 ′ , T 2 ′ ) (O'_2,T'_2) ( O 2 ′ , T 2 ′ ) . By Claim 13 , this preserves the required block structure. The subsequent recursive call preserves it by induction.
Base-Level Sorting. By Claim 9 , inserting the selected element into T 2 T_2 T 2 preserves its internal invariants.
If O 3 O_3 O 3 is a level-1 section, removing its minimum and shifting the remaining elements preserves their sorted order. Otherwise, the remaining operations preserve Base-Level Sorting by Claim 13 and the induction hypothesis.
If O 3 O_3 O 3 is a level-1 section, no further changes in cell ownership occur. Otherwise, SwapHole restores the size invariants of all affected sections by Claim 13. The recursive call preserves these invariants by induction.
First, suppose O 3 O_3 O 3 is a level-1 section. If T 2 T_2 T 2 is nonempty, the Block Ordering invariant gives T 2 < O 3 T_2 < O_3 T 2 < O 3 . Otherwise, we use O 2 < O 3 O_2 < O_3 O 2 < O 3 . Thus, moving min O 3 \min O_3 min O 3 into T 2 T_2 T 2 preserves the required ordering between the sections.
Now suppose O 3 O_3 O 3 consists of three blocks, and write
O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ . O_3 = O'_1 \mid T'_2 \mid O'_2 \mid O'_3. O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ .
If T 2 T_2 T 2 is nonempty, the Block Ordering invariant gives
O 1 ′ < T 2 < O 2 ′ . O'_1 < T_2 < O'_2. O 1 ′ < T 2 < O 2 ′ .
Hence, moving min O 2 ′ \min O'_2 min O 2 ′ into T 2 T_2 T 2 preserves both inequalities: the inserted element is larger than every element of O 1 ′ O'_1 O 1 ′ and smaller than every element remaining in O 2 ′ O'_2 O 2 ′ .
If T 2 T_2 T 2 is empty, the same conclusion follows from O 1 ′ < O 2 ′ O'_1 < O'_2 O 1 ′ < O 2 ′ .
Moreover, since O 2 < O 3 O_2 < O_3 O 2 < O 3 , the inserted element is larger than every element of O 2 O_2 O 2 . Thus, the Block Ordering invariant of S S S is also preserved.
Consequently, the insertion satisfies all required ordering constraints. By Claims 9 and 13, the subsequent operations preserve the affected ordering invariants, and the recursive call does so by induction.
It remains to verify that the hole reaches the end of S S S . If O 3 O_3 O 3 is a level-1 section, shifting its remaining elements moves the hole directly to the end of S S S . Otherwise, after SwapHole ( O 2 ′ , T 2 ′ ) (O'_2,T'_2) ( O 2 ′ , T 2 ′ ) , rebuilding may already have moved the hole to the end of O 3 O_3 O 3 or an enclosing section, in which case the operation is complete. If not, the hole is at the end of T 2 ′ T'_2 T 2 ′ , and the induction hypothesis applies to O 3 O_3 O 3 .
In either case, the hole reaches the last position of S S S , and all structural invariants are preserved.
Proof of Claim 16. We prove the claim by induction on i i i .
For i = 1 i = 1 i = 1 , the DST is a sorted array. Shifting its elements one position to the left moves the hole to the last position and preserves all invariants.
Assume now that i > 1 i > 1 i > 1 . If the DST consists of a single block with original section O O O , the claim follows directly from the induction hypothesis applied to O O O .
Otherwise, write
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . S = O_1 \mid T_2 \mid O_2 \mid O_3. S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 .
By the induction hypothesis, the recursive call to SimpleStart2End ( i − 1 ) (i - 1) ( i − 1 ) moves the hole to the end of O 1 O_1 O 1 while preserving its invariants. We then move x = min O 2 x = \min O_2 x = min O 2 into the hole using InsertMax, apply SwapHole ( O 2 , T 2 ) (O_2,T_2) ( O 2 , T 2 ) , and finally invoke JumpDown ( i ) (i) ( i ) . We verify that these operations preserve all structural invariants.
Block Sizes. The InsertMax operation does not change cell ownership. Any size violations caused by SwapHole, including the possible exhaustion of O 2 O_2 O 2 , are repaired using ReBuild. By Claim 11, these repairs restore the required size bounds. The remaining operations preserve the invariant by induction and Claim 14.
O 1 < O 2 < T 2 , O 2 < O 3 . O_1 < O_2 < T_2,\qquad O_2 < O_3. O 1 < O 2 < T 2 , O 2 < O 3 .
Since x = min O 2 x = \min O_2 x = min O 2 , moving x x x into O 1 O_1 O 1 preserves these relations: x x x is larger than every element of O 1 O_1 O 1 and smaller than all remaining elements of O 2 O_2 O 2 , as well as every element of T 2 T_2 T 2 and O 3 O_3 O 3 .
Moreover, SimpleStart2End is only applied when S S S is not the last original section of a three-block parent. Thus, there is no higher-level transfer section whose ordering with O 1 O_1 O 1 could be violated. The operation preserves the set of elements in S S S , so the remaining ordering constraints involving sections outside S S S are unchanged.
Finally, SwapHole and JumpDown preserve the ordering invariants by Claims 13 and 14.
It remains to verify the position of the hole. After moving x x x into O 1 O_1 O 1 , the hole is at the beginning of O 2 O_2 O 2 . The SwapHole operation moves it to the end of T 2 T_2 T 2 , and JumpDown ( i ) (i) ( i ) moves it to the last position of S S S . If rebuilding has already moved the hole to the end of S S S or an enclosing section, the remaining operations terminate.
Thus, SimpleStart2End ( i ) (i) ( i ) preserves all structural invariants and moves the hole to the last position, completing the induction. □
Proof of Claim 18. We prove the claim by induction on i i i .
For i = 1 i = 1 i = 1 , the DST is a sorted array. Shifting its elements one position to the left moves the hole to the last position and preserves all invariants.
Assume now that i > 1 i > 1 i > 1 . If the DST consists of a single block with original section O O O , the claim follows from the induction hypothesis applied to O O O .
Otherwise, write
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 . S = O_1 \mid T_2 \mid O_2 \mid O_3. S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 .
We first apply SimpleStart2End ( i − 1 ) (i - 1) ( i − 1 ) to O 1 O_1 O 1 . By Claim 16, this moves the hole to the end of O 1 O_1 O 1 while preserving its invariants.
If S S S is not the last original section of a three-block parent with a nonempty transfer section, the remaining operations are those of SimpleStart2End, and correctness follows from Claim 16.
It remains to consider the exceptional case, where
S ^ = O ^ 1 ∣ T ^ 2 ∣ O ^ 2 ∣ S , \widehat{S} = \widehat{O}_1 \mid\widehat{T}_2 \mid\widehat{O}_2 \mid S, S = O 1 ∣ T 2 ∣ O 2 ∣ S ,
and T ^ 2 \widehat{T}_2 T 2 is nonempty. We move min T ^ 2 \min\widehat{T}_2 min T 2 into O 1 O_1 O 1 using InsertMax, apply SimpleStart2End (i i i ) to T ^ 2 \widehat{T}_2 T 2 , and then move min O 2 \min O_2 min O 2 into T ^ 2 \widehat{T}_2 T 2 using InsertMax. Finally, we apply SwapHole (O 2 , T 2 O_2,T_2 O 2 , T 2 ) and JumpDown (i i i ) to S S S .
We verify that these operations preserve all structural invariants.
Number and Structure of Blocks. The InsertMax operations do not change the recursive structure. The calls to SimpleStart2End, SwapHole, and JumpDown preserve this invariant by Claims 13, 14 and 16, including any rebuilding they trigger.
Base-Level Sorting. Since O 1 < T ^ 2 O_1 < \widehat{T}_2 O 1 < T 2 , inserting min T ^ 2 \min\widehat{T}_2 min T 2 at the end of O 1 O_1 O 1 preserves its internal invariants by Claim 9. Similarly, since T ^ 2 < O 2 \widehat{T}_2 < O_2 T 2 < O 2 , inserting min O 2 \min O_2 min O 2 at the end of T ^ 2 \widehat{T}_2 T 2 preserves its internal invariants.
All other operations preserve base-level sorting by the correctness of SimpleStart2End, SwapHole, and JumpDown.
Block Sizes. The InsertMax operations do not change cell ownership and hence do not affect block sizes. Any violations caused by SwapHole, including the possible exhaustion of O 2 O_2 O 2 , are repaired using ReBuild. By Claim 11, these repairs restore the required size bounds. The remaining operations preserve this invariant by the preceding correctness claims.
O 1 < T ^ 2 < O 2 < T 2 , O 2 < O 3 , O_1 < \widehat{T}_2 < O_2 < T_2,\qquad O_2 < O_3, O 1 < T 2 < O 2 < T 2 , O 2 < O 3 ,
as well as
O ^ 2 < T ^ 2 , O ^ 2 < S . \widehat{O}_2 < \widehat{T}_2,\qquad\widehat{O}_2 < S. O 2 < T 2 , O 2 < S .
First, moving min T ^ 2 \min\widehat{T}_2 min T 2 into O 1 O_1 O 1 preserves O 1 < T ^ 2 O_1 < \widehat{T}_2 O 1 < T 2 , since the transferred element is smaller than every remaining element of T ^ 2 \widehat{T}_2 T 2 . It also preserves O 1 < O 2 O_1 < O_2 O 1 < O 2 , since T ^ 2 < O 2 \widehat{T}_2 < O_2 T 2 < O 2 .
The subsequent call to SimpleStart2End on T ^ 2 \widehat{T}_2 T 2 preserves its set of stored elements and therefore does not affect these ordering relations.
Next, moving min O 2 \min O_2 min O 2 into T ^ 2 \widehat{T}_2 T 2 preserves T ^ 2 < O 2 \widehat{T}_2 < O_2 T 2 < O 2 , since the transferred element is larger than every remaining element of T ^ 2 \widehat{T}_2 T 2 and smaller than every remaining element of O 2 O_2 O 2 . Moreover, since O 2 < T 2 O_2 < T_2 O 2 < T 2 and O 2 < O 3 O_2 < O_3 O 2 < O 3 , the inserted element is also smaller than every element of T 2 T_2 T 2 and O 3 O_3 O 3 . Thus, all ordering constraints between these sections are preserved.
The ordering constraints O ^ 2 < T ^ 2 \widehat{O}_2 < \widehat{T}_2 O 2 < T 2 and O ^ 2 < S \widehat{O}_2 < S O 2 < S also remain valid, since O ^ 2 \widehat{O}_2 O 2 was smaller than every element of both sections before the transfers. Furthermore, the transfers preserve the multiset of elements in S ^ \widehat{S} S , while leaving O ^ 1 \widehat{O}_1 O 1 and O ^ 2 \widehat{O}_2 O 2 unchanged. Hence, ordering constraints involving higher-level sections are preserved.
Finally, SwapHole and JumpDown preserve the ordering invariants by Claims 13 and 14.
It remains to verify the position of the hole. After moving min T ^ 2 \min\widehat{T}_2 min T 2 into O 1 O_1 O 1 , the hole is at the beginning of T ^ 2 \widehat{T}_2 T 2 . The call to SimpleStart2End (i i i ) moves it to the end of T ^ 2 \widehat{T}_2 T 2 , after which moving min O 2 \min O_2 min O 2 leaves the hole at the beginning of O 2 O_2 O 2 .
The SwapHole operation moves this hole to the end of T 2 T_2 T 2 , and JumpDown (i i i ) moves it to the last position of S S S . As usual, if rebuilding has already moved the hole to the end of S S S or an enclosing section, the remaining operations terminate.
Thus, Start2End (i i i ) preserves all structural invariants and moves the hole to the last position of the DST, completing the induction.
Proof of Claim 20. We prove the claim by induction on i i i .
For i = 1 i = 1 i = 1 , the DST is a sorted array. Shifting the elements following the hole one position to the left preserves its sorted order and moves the hole to the last position.
Assume now that i > 1 i > 1 i > 1 . If the DST consists of a single block with original section O O O , the claim follows from the induction hypothesis applied to O O O .
Otherwise, write
S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 , S = O_1 \mid T_2 \mid O_2 \mid O_3, S = O 1 ∣ T 2 ∣ O 2 ∣ O 3 ,
and let A A A be the section containing the hole. By the induction hypothesis, the initial call to Any2End (i − 1 i - 1 i − 1 ) moves the hole to the end of A A A while preserving all invariants.
We verify that the remaining operations preserve the four structural invariants.
O 2 < O 3 , O 2 < T 2 , O_2 < O_3,\qquad O_2 < T_2, O 2 < O 3 , O 2 < T 2 ,
the inserted element is larger than every remaining element of O 2 O_2 O 2 . Thus, InsertMax preserves its internal invariants by Claim 9. All subsequent operations preserve base-level sorting by their correctness claims.
Block Sizes. Moving an element into the hole does not change cell ownership, since its previous cell becomes the new hole. Any size violations caused by SwapHole, including the possible exhaustion of a middle original section, are handled by ReBuild. By Claims 11 and 13, these repairs restore the required size bounds. The remaining operations preserve the invariant by their correctness claims.
If A = O 3 A = O_3 A = O 3 , no further operations are required. If A = T 2 A = T_2 A = T 2 , we apply JumpDown, which preserves all ordering invariants by Claim 14.
If A = O 1 A = O_1 A = O 1 , we perform the remaining steps of Start2End. These steps require only that the hole is at the end of O 1 O_1 O 1 and that the ordering invariants hold, both of which follow from the induction hypothesis. Thus, correctness follows from the same argument as Claim 18, including the ordering constraints involving a higher-level transfer section.
It remains to consider A = O 2 A = O_2 A = O 2 . We distinguish two cases according to the element moved into the hole.
If T 2 T_2 T 2 is empty or min O 3 < min T 2 \min O_3 < \min T_2 min O 3 < min T 2 , we move x = min O 3 x = \min O_3 x = min O 3 into O 2 O_2 O 2 . Since O 2 < O 3 O_2 < O_3 O 2 < O 3 , the new element is smaller than every remaining element of O 3 O_3 O 3 , preserving O 2 < O 3 O_2 < O_3 O 2 < O 3 . Moreover, if T 2 T_2 T 2 is nonempty, then x < min T 2 x < \min T_2 x < min T 2 , so O 2 < T 2 O_2 < T_2 O 2 < T 2 is also preserved. The subsequent call to Start2End on O 3 O_3 O 3 preserves the remaining ordering constraints, including those involving T 2 T_2 T 2 , by Claim 18.
Otherwise, T 2 T_2 T 2 is nonempty and min T 2 < min O 3 \min T_2 < \min O_3 min T 2 < min O 3 . We first observe that O 3 O_3 O 3 must be a level-1 section. Indeed, otherwise O 3 O_3 O 3 consists of three blocks, and writing
O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ , O_3 = O'_1 \mid T'_2 \mid O'_2 \mid O'_3, O 3 = O 1 ′ ∣ T 2 ′ ∣ O 2 ′ ∣ O 3 ′ ,
the ordering invariant O 1 ′ < T 2 O'_1 < T_2 O 1 ′ < T 2 would imply min O 3 < min T 2 \min O_3 < \min T_2 min O 3 < min T 2 , a contradiction. Since O 3 O_3 O 3 is a level-1 section, the terminal ordering invariant gives T 2 < O 3 T_2 < O_3 T 2 < O 3 . We move x = min T 2 x = \min T_2 x = min T 2 into O 2 O_2 O 2 . The relations
O 2 < x < T 2 ∖ { x } < O 3 O_2 < x < T_2 \setminus\{x\} < O_3 O 2 < x < T 2 ∖ { x } < O 3
show that all ordering constraints between these sections are preserved. We then apply SimpleStart2End to T 2 T_2 T 2 and JumpDown to S S S . By Claims 14 and 16, these operations preserve all ordering invariants.
Finally, we verify the ordering constraints involving sections outside S S S . The case A = O 1 A = O_1 A = O 1 is already covered by Claim 18. In the other cases, the operations preserve the multiset of elements in S S S and do not modify O 1 O_1 O 1 .
In particular, if S S S is the last original section of a three-block parent with nonempty transfer section T ^ 2 \widehat{T}_2 T 2 , the additional ordering constraint is
O 1 < T ^ 2 < O 2 . O_1 < \widehat{T}_2 < O_2. O 1 < T 2 < O 2 .
In the case A = O 2 A = O_2 A = O 2 , the elements moved into O 2 O_2 O 2 come from T 2 T_2 T 2 or O 3 O_3 O 3 , both of which lie above T ^ 2 \widehat{T}_2 T 2 by the ordering constraints before the hole was created. Thus, this constraint is preserved. All other external ordering constraints are preserved as well.
It remains to verify the position of the hole. After the initial recursive call, the hole is at the end of A A A .
If A = O 3 A = O_3 A = O 3 , it has already reached the end of S S S . If A = T 2 A = T_2 A = T 2 , JumpDown moves it to the end of S S S . If A = O 1 A = O_1 A = O 1 , the remaining steps of Start2End complete the movement.
If A = O 2 A = O_2 A = O 2 , moving the minimum of O 3 O_3 O 3 or T 2 T_2 T 2 leaves the hole at the beginning of the corresponding section, by Claim 6. In the first case, Start2End moves the hole to the end of O 3 O_3 O 3 , and hence of S S S . In the second case, SimpleStart2End moves the hole to the end of T 2 T_2 T 2 , after which JumpDown moves it to the end of S S S .
As usual, if rebuilding has already moved the hole to the end of S S S or an enclosing section, the remaining operations terminate.
Thus, Any2End (i) preserves all structural invariants and moves the hole to the last position of the DST, completing the induction.
Omitted Proofs from sec:fully-dynamic-lowcost
Proof of Claim 23. We first verify that every Re-Sort operation can reconstruct the corresponding A-DST as a single DST of the same level.
Consider a level-j j j auxiliary A-DST A j A_j A j , where j < d j < d j < d . Whenever Re-Sort ( j + 1 ) (j+1) ( j + 1 ) or a higher-level reconstruction is performed, A j A_j A j becomes empty. Before the next such reconstruction, at most 2 j 2^j 2 j updates occur, each increasing the number of cells in A j A_j A j by at most one. Thus, even during an update,
∣ A j ∣ ≤ 2 j . |A_j| \le2^j. ∣ A j ∣ ≤ 2 j .
The entire level-d d d A-DST contains n ≤ 2 d n \le2^d n ≤ 2 d cells, so the same bound holds at the top level. Consequently, whenever Re-Sort ( i ) (i) ( i ) is invoked, it reconstructs at most 2 i 2^i 2 i cells. The recursive construction used by Rebuild can accommodate this size, as established in Claim 11. Indeed, the rebuilding rule constructs a valid level-i i i DST from any collection of at most 24 ⋅ 2 i − 1 24 \cdot2^{i-1} 24 ⋅ 2 i − 1 cells, which is more than sufficient. We now verify the structural invariants.
DST Invariants. The elements are sorted and reconstructed into a clean level-i i i DST, with all transfer sections empty. By Claim 11 , the new DST satisfies the Number of Blocks, Block Sizes, Block Ordering, and Base-Level Sorting invariants.
All components outside the rebuilt A-DST remain unchanged. Since no ordering is required between different components, their invariants remain satisfied.
The total number of cells in the rebuilt level-i i i A-DST remains unchanged. Therefore, the sizes of all enclosing auxiliary A-DSTs are unchanged as well, preserving their bounds.
Thus, Re-Sort maintains all structural invariants of the A-DST.
Proof of Claim 25. We verify the Suffix Sizes invariant and the internal DST invariants separately.
By the Re-Sort schedule, at most 2 j − 1 2^j-1 2 j − 1 completed updates occur before the next update that triggers such a reconstruction. Each update can transfer at most one cell into A j A_j A j , since the hole crosses its left boundary at most once.
Thus, during the current update, including the temporary hole, we have
∣ A j ∣ ≤ ( 2 j − 1 ) + 1 = 2 j . |A_j| \le(2^j-1)+1 = 2^j. ∣ A j ∣ ≤ ( 2 j − 1 ) + 1 = 2 j .
Rebuilding within a component does not change the total number of cells in A j A_j A j . Hence the Suffix Sizes invariant is preserved.
For rebuilt sections not containing the hole, correctness follows from Claims 11 and 13 . In the receiving component D ′ D' D ′ , every section containing the hole lies along its chain of first original sections, with the hole in its first cell. In particular, such a section is never the last original section of a three-block parent.
We rebuild these sections by treating the hole as the smallest element. This leaves the hole in the first cell, while sorting the stored elements and emptying the transfer sections. The same block-size construction as in ReBuild restores the structural invariants. Moreover, since the set of stored elements in each rebuilt section is unchanged, the ordering constraints with surrounding sections remain satisfied.
Finally, the Suffix Sizes bound guarantees sufficient capacity for rebuilding the root sections. Since the A-DST imposes no ordering constraints between distinct components, no additional conditions are required. Thus, all structural invariants of the A-DST are preserved, and the hole remains in the first cell of D ′ D' D ′ .
Proof of Claim 26. We charge the recourse incurred by ReBuild to changes in cell ownership caused by SwapHole. Consider a repair triggered by a level-( i + 1 ) (i+1) ( i + 1 ) section S S S , and let q = 2 i q = 2^i q = 2 i . The repair rebuilds S S S , or its parent if S S S is the last original section of a three-block parent. We include all recursive rebuilding in the cost of this repair.
Cost of rebuilding. The section S S S contains at most 24 q 24q 24 q cells, by the size bound of its enclosing block, or by the capacity bound if S S S is a root. If we rebuild its parent instead, the parent’s first and last blocks each contain fewer than 24 q 24q 24 q cells, and its middle block contains 2 q 2q 2 q cells. Thus, the repair incurs at most 50 q 50q 50 q recourse.
Changes required for rebuilding. We show that each repair requires at least q / 2 q/2 q /2 preceding changes in cell ownership, distinguishing the two rebuilding conditions.
2 q ≤ ∣ O 1 ∣ ≤ 23 q / 2 , 8 q ≤ ∣ O 3 ∣ ≤ 23 q / 2. 2q \le\lvert O_1\rvert\le23q/2,\qquad8q \le\lvert O_3\rvert\le23q/2. 2 q ≤ ∣ O 1 ∣ ≤ 23 q /2 , 8 q ≤ ∣ O 3 ∣ ≤ 23 q /2.
The permitted bounds are ∣ S ∣ < 12 q \lvert S\rvert< 12q ∣ S ∣ < 12 q for a single block, and
q ≤ ∣ O 1 ∣ < 12 q , 7 q ≤ ∣ O 3 ∣ < 12 q q \le\lvert O_1\rvert< 12q,\qquad7q \le\lvert O_3\rvert< 12q q ≤ ∣ O 1 ∣ < 12 q , 7 q ≤ ∣ O 3 ∣ < 12 q
for three blocks.
For a single block, reaching the upper bound of 12 q 12q 12 q requires at least q q q increases in size. For three blocks, violating either lower bound requires more than q q q decreases, while reaching the upper bound of 12 q 12q 12 q requires at least q / 2 q/2 q /2 increases. Since each change in cell ownership changes a block size by at most one, any violation requires at least q / 2 q/2 q /2 such changes since the block sizes were last chosen.
Empty original section of the middle block. If O 2 O_2 O 2 becomes empty, then ∣ T 2 ∣ = q \lvert T_2\rvert= q ∣ T 2 ∣ = q , since the middle block contains exactly q q q cells. As T 2 T_2 T 2 was empty after its previous reconstruction, at least q q q cells must have entered it since then.
Thus, each repair costs at most 50 q 50q 50 q and can be charged to at least q / 2 q/2 q /2 preceding ownership changes, assigning at most 100 recourse to each.
Charging. It remains to show that each ownership change is charged only O ( d ) O(d) O ( d ) times. We charge each repair to the section S S S that triggered it, even if its parent is rebuilt instead. Fix such a section S S S .
For block-size violations, we charge the repair to ownership changes since the block sizes of S S S were last chosen. Each such repair chooses a new block division, so successive violations are charged to disjoint sets of changes. Rebuilding S S S without changing its block sizes does not reset this accounting.
For an empty middle original section, we charge the repair to transfers into T 2 T_2 T 2 since it was last emptied. Since rebuilding empties T 2 T_2 T 2 , successive violations of this type are also charged to disjoint sets of changes.
Rebuilding an ancestor may reconstruct S S S as well, but this incurs no separate charge, since its cost is included in the ancestor’s repair. If the reconstruction chooses new block sizes for S S S , the accounting for size violations restarts; otherwise, it is preserved. The accounting for an empty middle section restarts whenever T 2 T_2 T 2 is emptied.
Thus, each ownership change is charged at most once for each of the two violation types in a given section. Since each SwapHole changes cell ownership along at most two recursive paths, it affects only O ( 1 ) O(1) O ( 1 ) sections at each of the d d d levels. Consequently, each SwapHole receives O ( d ) O(d) O ( d ) charge, giving a total rebuilding recourse of O ( d M ) O(dM) O ( d M ) .
Proof of Claim 27. Let D j D_j D j be the component containing the deleted element x x x . After removing x x x , we apply Any2End (j j j ), which moves the resulting hole to the last cell of D j D_j D j while preserving its structural invariants, by Claim 20.
We then process the remaining components from left to right. At each step, SwapHole transfers ownership of the empty cell from the current component to the next one, where it becomes the first cell. By Claim 25 , this preserves the structural invariants of the participating components. We then apply Start2End to move the hole to the last cell of the next component, preserving its invariants by Claim 18 . Repeating this procedure brings the hole to the last cell of D 1 D_1 D 1 , which is also the last position of the A-DST.
We now verify the structural invariants.
Number of Blocks. By Claims 18 , 20 and 25 , the operations preserve the recursive structure of each participating DST, using ReBuild when necessary.
Block Sizes. Transferring the hole between components changes their numbers of cells. By the same correctness claims, any resulting violations of the Block Sizes invariant are repaired using ReBuild, whose correctness follows from Claim 11 .
Base-Level Sorting. By the correctness of Any2End, SwapHole, and Start2End, every level-1 section remains sorted. In particular, the final component D 1 = A 1 D_1 = A_1 D 1 = A 1 remains sorted.
Suffix Sizes. Recall that A k A_k A k is the suffix consisting of components D k , … , D 1 D_k,\ldots,D_1 D k , … , D 1 , and that ∣ A k ∣ |A_k| ∣ A k ∣ counts all cells, including holes.
During the deletion, the only operation that can increase ∣ A k ∣ |A_k| ∣ A k ∣ is the transfer of the hole from D k + 1 D_{k+1} D k + 1 into D k D_k D k . This transfer adds exactly one cell to A k A_k A k . Since the hole moves through the components from left to right, this boundary is crossed at most once. Thus, each deletion increases ∣ A k ∣ |A_k| ∣ A k ∣ by at most one.
It remains to bound the accumulated increase. Initially, A k A_k A k is empty. Moreover, each execution of Re-Sort (k + 1 k+1 k + 1 ), or of a higher-level Re-Sort, reconstructs the corresponding structure with A k A_k A k empty. By the rebuilding schedule, at most 2 k 2^k 2 k deletion–insertion updates occur between consecutive such reconstructions.
Since each deletion increases ∣ A k ∣ |A_k| ∣ A k ∣ by at most one, while the subsequent insertion does not change cell ownership, we obtain
∣ A k ∣ ≤ 2 k . |A_k| \le2^k. ∣ A k ∣ ≤ 2 k .
This bound also holds during the deletion immediately preceding a scheduled Re-Sort.
Consequently, all structural invariants are preserved, and the hole is at the last cell of A 1 A_1 A 1 , ready for the subsequent insertion.
Proof of Claim 28. By Claim 27, the preceding deletion preserves the structural invariants and leaves a hole at the last position of the A-DST, inside A 1 A_1 A 1 .
The INSERT operation inserts the new element in sorted order into A 1 A_1 A 1 , using this existing hole. Since A 1 A_1 A 1 is a level-1 DST, this preserves the Base-Level Sorting invariant.
Moreover, the insertion does not change the number of cells or their ownership by sections. In particular, the sizes of all blocks and auxiliary A-DSTs remain unchanged, since holes are counted toward their sizes. All other components are unaffected. Thus, the Number of Blocks, Block Sizes, Block Ordering, and Suffix Sizes invariants remain satisfied.
Finally, any scheduled RE-SORT is performed after the insertion and preserves the invariants by Claim 23. □