University of Copenhagen,
Denmarkmiab@di.ku.dkhttps://orcid.org/0000-0003-2734-4690Supported by Starting
Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere
Aude research career programme and part of Basic Algorithms Research
Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. KTH Royal
Institute of Technology, Stockholm,
Swedenbercea@kth.sehttps://orcid.org/0000-0001-8430-2441 University of
California, Santa Cruz,
USAlorenzo2beretta@gmail.comhttps://orcid.org/0000-0002-4676-9777 University
of Copenhagen, Denmarkjokl@di.ku.dkhttps://orcid.org/0000-0002-7403-417X
Institut für Informatik, Freie Universität Berlin, Germanylaszlo.kozma@fu-
berlin.dehttps://orcid.org/0000-0002-3253-2373Supported by DFG grant KO
6140/1-2. Mikkel Abrahamsen, Ioana O. Bercea, Lorenzo Beretta, Jonas Klausen,
László Kozma _Ioana O. Bercea, Lorenzo Beretta and Jonas Klausen:_ Supported
by grant 16582, Basic Algorithms Research Copenhagen (BARC), from the VILLUM
Foundation. [500]Theory of computation Design and analysis of algorithms
Timothy Chan, Johannes Fischer, John Iacono, and Grzegorz Herman 4 32nd Annual
European Symposium on Algorithms (ESA 2024) ESA 2024 ESA 2024 September 2–4,
2024 Royal Holloway, London, United Kingdom 308 56

# Online sorting and online TSP:
randomized, stochastic, and high-dimensional

Mikkel Abrahamsen  Ioana O. Bercea  Lorenzo Beretta  Jonas Klausen  László
Kozma

###### Abstract

In the _online sorting problem_ , $n$ items are revealed one by one and have
to be placed (immediately and irrevocably) into empty cells of a size-$n$
array. The goal is to minimize the sum of absolute differences between items
in consecutive cells. This natural problem was recently introduced by Aamand,
Abrahamsen, Beretta, and Kleist (SODA 2023) as a tool in their study of online
geometric packing problems. They showed that when the items are reals from the
interval $[0,1]$ a competitive ratio of $O(\sqrt{n})$ is achievable, and no
deterministic algorithm can improve this ratio asymptotically.

In this paper, we extend and generalize the study of online sorting in three
directions:

  * •

_randomized_ : we settle the open question of Aamand et al. by showing that
the $O(\sqrt{n})$ competitive ratio for the online sorting of reals cannot be
improved even with the use of randomness;

  * •

_stochastic_ : we consider inputs consisting of $n$ samples drawn uniformly at
random from an interval, and give an algorithm with an improved competitive
ratio of $\widetilde{O}(n^{1/4})$. The result reveals connections between
online sorting and the design of efficient hash tables;

  * •

_high-dimensional_ : we show that $\widetilde{O}(\sqrt{n})$-competitive online
sorting is possible even for items from $\mathbb{R}^{d}$, for arbitrary fixed
$d$, in an adversarial model. This can be viewed as an online variant of the
classical TSP problem where tasks (cities to visit) are revealed one by one
and the salesperson assigns each task (immediately and irrevocably) to its
timeslot. Along the way, we also show a tight $O(\log{n})$-competitiveness
result for _uniform metrics_ , i.e., where items are of different _types_ and
the goal is to order them so as to minimize the _number of switches_ between
consecutive items of different types.

###### keywords:

sorting, online algorithm, TSP

###### category:

##  1 Introduction

The following natural problem called _online sorting_ was recently introduced
by Aamand, Abrahamsen, Beretta, and Kleist [1]: Given a sequence
$x_{1},\dots,x_{n}$ of real values, assign them bijectively to array cells
$A[1],\dots,A[n]$. Crucially, after receiving $x_{j}$, for $j=1,2,\dots,n$, we
must immediately and irrevocably set $A[i]=x_{j}$, for some previously unused
array index $i\in[n]$. The goal is to minimize
$\sum_{i=1}^{n-1}{\left|A[i+1]-A[i]\right|}$, the sum of absolute differences
between items in consecutive cells.

Aamand et al. [1] study the problem as modelling certain geometric online
packing problems. In particular, they use it to show lower bounds on the
competitive ratio of such problems111The _competitive ratio_ of an online
algorithm is the worst-case ratio of its cost to the optimum (offline) cost
over inputs of a certain size $n$. The competitive ratio of a problem is the
best competitive ratio achievable by an online algorithm for the problem. . It
is easy to see that the optimal (offline) solution of online sorting is to
place the entries in sorted (increasing) order, and the question is how to
approximate this solution in an online setting where the items are revealed
one by one.

The problem evokes familiar scenarios where we must commit _step-by-step_ to
an ordering of items, such as when scheduling meetings in a calendar, writing
recipes in a notebook, planting trees in a garden, or writing data into memory
cells. In such situations, some local coherence or sortedness is often
desirable, but once the location of an item has been assigned, it is expensive
to change it; for instance, it may be difficult to reschedule meetings or to
migrate data items once memory locations are referenced from elsewhere. One
must then carefully balance between placing similar items next to each other
and leaving sufficiently large gaps amid uncertainty about future
arrivals222The cost measure of online sorting is also natural as a measure of
the _unsortedness_ of a sequence. For this, the _number of inversions_ (i.e.,
the number of pairs $a<b$ where $b$ appears before $a$) is perhaps more widely
used. We argue, however, that with this latter cost, one cannot obtain a
nontrivial competitive ratio. Consider an adversary that outputs $n/2$ copies
of $0.5$, followed by either all $0$s or all $1$s until the end. It is easy to
see that one of these choices results in at least $n^{2}/8$ inversions for any
online algorithm, whereas the optimal (sorted) sequence has zero inversions..

Moreover, online sorting can be firmly placed among familiar and well-studied
online problems; we briefly mention two. As they differ from online sorting in
crucial aspects, a direct transfer of techniques appears difficult.

  * •

_list labeling_ or _order maintenance_ [16, 11, 6, 26, 7]: in this problem, a
sequence of values are to be assigned labels consistent with their ordering
(in effect placing the values into an array). The main difference from online
sorting is that the sequence must be fully sorted and the goal is to minimize
_recourse_ , i.e., movement of previously placed items.

  * •

_matching on the line_ [15, 24, 14, 4]: here, a sequence of clients (e.g.,
drawn from $[n]$) are to be matched uniquely and irrevocably to servers (say,
locations in $[n]$). The problem differs from online sorting mainly in its
cost function; the goal here is to minimize the sum of distances between
matched client-server pairs.

One of the main results of Aamand et al. [1] is an algorithm for online
sorting with competitive ratio $O(\sqrt{n})$. Aamand et al. require the input
entries to come from the unit interval $[0,1]$ and to contain the endpoints
$0$ and $1$. Conveniently, this makes the offline cost equal to $1$ and the
competitive ratio equal to the online cost. We show that the same
competitiveness result can be obtained even if these assumptions are relaxed.

Aamand et al. [1] also show that the $O(\sqrt{n})$ bound cannot be improved by
any deterministic algorithm, and leave it as an open question whether it can
be improved through randomization (assuming that the adversary is oblivious,
i.e., that it does not know the “coin flips” of our algorithm). Note that in
several online problems such as _paging_ or _$k$ -server_, randomization can
lead to asymptotic improvements in competitiveness (against an oblivious
adversary); e.g., see [10]. As our first main result, we show that for online
sorting, randomization (essentially) does not help.

######  Theorem 1.1.

The (deterministic and randomized) competitive ratio of online sorting is
$\Theta(\sqrt{n})$. The lower bound $\Omega(\sqrt{n})$ holds even when the
input numbers are from $[0,1]$.

Online TSP. Ordering real values with the above cost (sum of differences
between consecutive items) can be naturally viewed as a one-dimensional
variant of the Traveling Salesperson Problem (TSP). Suppose that $n$ cities
are revealed one by one (with repetitions allowed), and a salesperson must
decide, for each occurrence $c$ of a city, on a timeslot for visiting $c$,
i.e., the position of $c$ in the eventual tour. The cost is then the length of
the fully constructed tour333A small technicality is whether the salesperson
must return to the starting point or not. The effect of this in our cost
regime, however, is negligible.. Formally, given a sequence
$(x_{1},\dots,x_{n})$ of items $x_{i}\in{S}$, for a metric space $S$ with
distance function $d(\cdot,\cdot)$, the goal is to assign the items
bijectively to array cells $A[1],\dots,A[n]$ in an online fashion such as to
minimize $\sum_{i=1}^{n-1}{d\left(A[i],A[i+1]\right)}$. We refer to this
problem444This model is sometimes referred to as the _online-list model_ ; it
has been considered mostly in the context of scheduling problems [23, 13]. To
our knowledge, TSP has not been studied in this setting before. Note however,
that a different online model, called the _online-time model_ has been used to
study TSP [3, 20, 9]. In that model new cities can be revealed while the
salesperson is already executing the tour; this may require changing the tour
on the fly. Results in the two models are not comparable. as _online TSP in
$S$_.

_Online TSP in $\mathbb{R}$_ is exactly online sorting. A natural
$d$-dimensional generalization is _online TSP in $\mathbb{R}^{d}$_, with the
Euclidean distance $d(\cdot,\cdot)$ between items.555One may also view this
task as a form of _dimensionality reduction_ : we seek to embed a
$d$-dimensional data set in a one-dimensional space (the array), while
preserving some distance information. A difficulty arising in dimensions two
and above is that the optimal cost is no longer constant; in $\mathbb{R}^{d}$,
the (offline) optimum may reach $\Theta(n^{1-\frac{1}{d}})$ even if the input
points come from a unit box. Computing the optimum exactly is NP-hard even if
$d=2$ [22]. Our second main result is an online algorithm whose cost is
$O(n^{1-\frac{1}{d+1}})$ and a competitiveness guarantee close to the one-
dimensional case.

######  Theorem 1.2.

There is a deterministic algorithm for online TSP in $\mathbb{R}^{d}$ with
competitive ratio $\sqrt{d}\cdot 2^{d}\cdot O(\sqrt{n\log{n}})$.

As this setting includes online sorting as a special case, the lower bound of
$\Omega(\sqrt{n})$ applies. A key step in obtaining Theorem 1.2 is the study
of the _uniform metric_ variant of the problem, i.e., the case of distance
function $d$ with $d(x,y)=1$ if and only if $x\neq y$. This captures the
natural problem where items (or tasks) fall into a certain number of _types_ ,
and we wish to order them such as to minimize the number of _switches_ , i.e.,
consecutive pairs of items of different types. For this case we prove a tight
(deterministic and randomized) competitive ratio, independent of the number of
different types, which may be of independent interest. Our algorithm is a
natural greedy strategy; we analyze it by modelling the evolution of
contiguous runs of empty cells as a coin-removal game between the algorithm
and adversary.

######  Theorem 1.3.

The competitive ratio of online sorting of $n$ items under the uniform metric
is $\Theta(\log{n})$. The upper bound $O(\log{n})$ is achieved by a
deterministic algorithm and the lower bound $\Omega(\log{n})$ also holds for
randomized algorithms.

Aamand et al. also consider the setting where the array is only partially
filled (placing $n$ items into $m>n$ cells). In this case, the cost is
understood as the sum of distances $d(x,y)$ over pairs of items $x,y$ with no
other item placed between them. We thus extend our previous result to arrays
of a larger size, obtaining a tight characterization.

######  Theorem 1.4.

The competitive ratio (deterministic and randomized) of online sorting of $n$
items with an array of size $\MT@delim@Auto\ceil@star{\gamma n}$, with
$\gamma>1$, under the uniform metric is
$\Theta(1+\log{\frac{\gamma}{\gamma-1}})$.

Stochastic input. Given the (rather large) $\Omega(\sqrt{n})$ lower bound on
the competitive ratio of online sorting, it is natural to ask whether we can
overcome this barrier by relaxing the worst-case assumption on the input. Such
a viewpoint has become influential recently in an attempt to obtain more
refined and more realistic guarantees in online settings (e.g., see [25, 14]).
A natural model is to view each item as drawn independently from some
distribution, e.g., uniformly at random from a fixed interval. Our next main
result shows an improved competitive ratio for such stochastic inputs:

######  Theorem 1.5.

There is an algorithm for online sorting of $n$ items drawn independently and
uniformly at random from $(0,1]$ that achieves competitive ratio $O((n\log
n)^{1/4})$ with probability at least $1-2/n$.

The algorithm illuminates a connection between online sorting and hash-based
dictionaries [19, § 6.4]. In the latter, the task is to place a sequence of
$n$ keys in an array of size $O(n)$, with the goal of minimizing _search
time_. Fast searches are achieved by hashing keys to locations in the array.
Due to hash collisions, not all elements can be stored exactly at their hashed
location, and various paradigms have been employed to ensure that they are
stored “nearby” (for the search to be fast). We adapt two such paradigms to
online sorting. The first is to hash elements into buckets and solve the
problem separately in each bucket. Each bucket has a fixed capacity, and so an
additional _backyard_ is used to store keys that do not fit in their hashed
bucket [2, 8]. In Theorem 1.5, we use the values of the entries to assign them
to buckets and employ a similar backyard design. We note some critical
technical differences: in our design, all buckets must be full and we solve
the problem recursively in each bucket; we also operate in a much tighter
balls-into-bins regime, as we are hashing $n$ elements into exactly $n$
locations.

When the array size is allowed to be bigger than $n$, we employ yet another
way for resolving hash collisions: the linear probing approach of Knuth [18].
Here, the value $\lceil\upalpha n\rceil$ serves as the hash location of an
entry $\upalpha\in(0,1)$. Intuitively, this is a good approximation for where
the entry would appear in the sorted order. If we make sure that we place the
entry close enough to this intended location, we can hope for a small overall
cost. That is, we use the fact that linear probing places similar values close
to each other. We get the following:

######  Theorem 1.6.

For any $\gamma>1$, there is an algorithm for online sorting of $n$ items
drawn independently and uniformly from $(0,1)$ into an array of size
$\MT@delim@Auto\ceil@star{\gamma n}$ that achieves expected competitive ratio
$O\left(1+\frac{1}{\gamma-1}\right)$.

Paper structure. In § 2 we present our results for the standard (one-
dimensional) online sorting, in particular the lower bound for the randomized
competitive ratio (Theorem 1.1). Results for online TSP in $\mathbb{R}^{d}$
and results for the uniform metric (Theorems 1.2, 1.3, 1.4) are in § 3. Our
results for online sorting with stochastic input (Theorems 1.5, 1.6) are in §
4. We conclude with a list of open questions in § 5. We defer some proofs and
remarks to the Appendix.

##  2 Competitiveness for online sorting

Given a sequence $X=(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$ and a bijection
$f\colon[n]\rightarrow[n]$ assigning “array cells” $A[i]=x_{f(i)}$, let
$\mathtt{D}_{f}(X)=\sum_{i=1}^{n-1}{|A[i+1]-A[i]|}$. Let $\mathtt{OPT}(X)$
denote the quantity $\min_{f}{\mathtt{D}_{f}(X)}$, i.e., the _offline
optimum_.

An _online_ algorithm is one that constructs the mapping $f$ incrementally.
Upon receiving $x_{j}$, for $j=1,\dots,n$, the algorithm immediately and
irrevocably assigns $f(i)=j$, for some previously unassigned $i\in[n]$. For an
online algorithm $\mathcal{A}$, we denote by $\mathcal{A}(X)$ the cost
$\mathtt{D}_{f}(X)$ for the function $f$ constructed by algorithm
$\mathcal{A}$ on input sequence $X$. We are interested in the competitive
ratio $\mathtt{C}_{\mathcal{A}}(n)$ of an algorithm $\mathcal{A}$, i.e., the
supremum of $\mathcal{A}(X)/\mathtt{OPT}(X)$ over all inputs $X$ of a certain
size $n$, and in the best possible competitive ratio
$\mathtt{C}=\mathtt{C}(n)=\inf_{\mathcal{A}}{\mathtt{C}_{\mathcal{A}}(n)}$
obtainable by any online algorithm $\mathcal{A}$ for a given problem.

Upper bound. Aamand et al. [1] show that $\mathtt{C}\in\Theta{(\sqrt{n})}$,
under the additional restrictions that $x_{i}\in[0,1]$ for all $i\in[n]$, and
that $\\{0,1\\}\subseteq\\{x_{1},\dots,x_{n}\\}$. As our first result, we
employ a careful doubling strategy to show the same upper bound without the
two restrictions, for general sequences of $n$ reals (the lower bound clearly
continues to hold).

######  Claim 1 (Proof in Appendix A).

There is a deterministic online algorithm $\mathcal{A}$ for online sorting of
an arbitrary sequence of $n$ reals, with $\mathtt{C}_{\mathcal{A}}\in
O(\sqrt{n})$.

Lower bound. The competitive ratio $\mathtt{C}_{\mathcal{A}}$ of a
_randomized_ algorithm $\mathcal{A}$ is the supremum of
$\mathbb{E}[\mathcal{A}(X)]/\mathtt{OPT}(X)$ over all inputs $X$, where the
expectation is over the random choices of $\mathcal{A}$. Aamand et al. [1]
leave open the question of whether a lower bound of $\Omega(\sqrt{n})$ on the
competitive ratio also holds for randomized algorithms. We settle this
question in the affirmative. It is important to emphasize that the random
choices of $\mathcal{A}$ are not known to the adversary, i.e., we assume the
_oblivious_ model [10].

######  Claim 2.

$\mathtt{C}_{\mathcal{A}}\in\Omega(\sqrt{n})$ for every (possibly randomized)
online algorithm $\mathcal{A}$.

In the remainder of the section we prove Claim 2, which implies Theorem 1.1.
As usual, to lower bound the performance of a randomized algorithm (a
distribution over deterministic algorithms), we lower bound instead the
performance of a deterministic algorithm on an (adversarially chosen)
distribution over input sequences.

Input distribution. Assume for simplicity that $\sqrt{n}$ is an integer.
Repeat the following until a sequence of length $n$ is obtained. With
probability $\frac{1}{2\sqrt{n}}$ set the remainder of the sequence to $0$s.
With probability $\frac{1}{2\sqrt{n}}$ set the remainder of the sequence to
$1$s. With probability $1-\frac{1}{\sqrt{n}}$ offer $\frac{k}{\sqrt{n}}$ for
$k=0,\dots,\sqrt{n}-1$ as the next $\sqrt{n}$ elements of the sequence, and
flip a new coin. We refer to the $\sqrt{n}$ elements produced by the third
option as an _epoch_. Notice that $\mathtt{OPT}\leq 1$, thus it is enough to
lower bound the expected cost of the algorithm.

Notation. Let $T$ be a partially filled array, $|T|$ be the number of stored
elements and $G(T)$ be the number of “gaps”, i.e., maximally contiguous groups
of empty cells.

Let $f(T)$ be the minimum cost of _filling_ $T$ by an online algorithm, when
the input sequence is chosen according to the distribution described above,
where the cost of two neighboring elements $T[i],T[i+1]$ are accounted for
when $T[i]$ or $T[i+1]$ is filled, whichever happens the latest.

More formally, define the cost of a partially filled array $T$ to be

$c(T)=\sum_{\begin{subarray}{c}i=0\\\ T[i],T[i+1]\text{ are
nonempty}\end{subarray}}^{n-1}\left|T[i]-T[i+1]\right|,$

and let $\mathcal{A}(T)$ be the final array produced by an online algorithm
$\mathcal{A}$ when the remaining $n-\left|T\right|$ elements of the input
sequence are generated as described above. Then $f(T)=c(\mathcal{A}(T))-c(T)$
is the difference between the final cost and the cost of the partially filled
array $T$. Thus $f(T)=0$ if $|T|=n$, and $\mathbb{E}[f(\emptyset)]$ is the
value we wish to bound, using $\emptyset$ for the empty array.

For mappings $T_{1},T_{2}$ where $T_{2}[i]=T_{1}[i]$ for all indices where
$T_{1}[i]$ is nonempty we say that $T_{2}$ can be obtained from $T_{1}$. For
such a pair of mappings let $c(T_{1},T_{2})=c(T_{2})-c(T_{1})$ be the cost of
transforming $T_{1}$ into $T_{2}$ according to the way of accounting given
above.

Let $\mathcal{T}(T)$ be the set of mappings that can be obtained by inserting
an epoch into $T$. That is, $\mathcal{T}(T)$ contains all mappings
$T^{\prime}$ which can be obtained from $T$ where the difference between
$T^{\prime}$ and $T$ corresponds to the elements of an epoch. Note that
$|T^{\prime}|=|T|+\sqrt{n}$ for $T^{\prime}\in\mathcal{T}(T)$.

Let $\mathcal{L}=\\{T\colon G(T)\leq\frac{\sqrt{n}}{8}\\}$ and
$\mathcal{H}=\\{T\colon G(T)>\frac{\sqrt{n}}{8}\\}$ be the sets of all
partially filled arrays with a low/high number of gaps.

######  Lemma 2.1.

Let $T_{1},T_{2}\in\mathcal{L}$ with $T_{2}\in\mathcal{T}(T_{1})$. Then
$c(T_{1},T_{2})\geq\frac{3}{16}$.

######  Proof 2.2.

If an element is placed between two empty cells, the number of gaps will
increase by one. If it is placed next to one or two occupied cells, the number
of gaps stays constant or is reduced by one – call such an insertion an
_attachment_. As $G(T_{2})\leq G(T_{1})+\frac{\sqrt{n}}{8}$ at least
$\frac{7\sqrt{n}}{16}$ of the $\sqrt{n}$ insertions of the epoch must be
attachments.

An attachment incurs cost at least $\frac{1}{\sqrt{n}}$ unless the value(s) in
the neighboring cell(s) and the newly inserted value are identical. As all
values within an epoch are distinct, an attachment can only be without cost if
the neighboring cell was occupied in $T_{1}$ (that is, before the epoch). As
$G(T_{1})\leq\frac{\sqrt{n}}{8}$ at most $\frac{\sqrt{n}}{4}$ occupied cells
border an empty cell. The remaining
$\sqrt{n}(\frac{7}{16}-\frac{1}{4})=\frac{3\sqrt{n}}{16}$ attachments will
incur non-zero cost.

As a shorthand, let $(T+0)$ and $(T+1)$ be the mappings obtained by filling
all gaps in $T$ with $0$s/$1$s, respectively.

######  Lemma 2.3.

$c(T,(T+0))+c(T,(T+1))\geq G(T).$

######  Proof 2.4.

Each gap in $T$ is bordered by at least one non-empty cell $A[i]$. We have
$|A[i]-0|+|A[i]-1|=1$.

For a mapping $T$ the expected remaining cost can be bounded from below by

$\mathbb{E}[f(T)]\geq\frac{1}{2\sqrt{n}}\cdot
c(T,(T+0))+\frac{1}{2\sqrt{n}}\cdot c(T,(T+1))\\\
+\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min_{T^{\prime}\in\mathcal{T}(T)}\\{c(T,T^{\prime})+\mathbb{E}[f(T^{\prime})]\\}$

and by Lemma 2.3 we thus have

$\displaystyle\mathbb{E}[f(T)]\geq\frac{G(T)}{2\sqrt{n}}+\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min_{T^{\prime}\in\mathcal{T}(T)}\\{c(T,T^{\prime})+\mathbb{E}[f(T^{\prime})]\\}\,.$
(1) $\displaystyle\textrm{Let\leavevmode\nobreak\
}\mathcal{L}(i)=\min_{\mathclap{\begin{subarray}{c}T\in\mathcal{L}\\\
|T|=n-i\cdot\sqrt{n}\end{subarray}}}{\leavevmode\nobreak\
\mathbb{E}[f(T)]},\mathrm{\quad
and\quad}\mathcal{H}(i)=\min_{\mathclap{\begin{subarray}{c}T\in\mathcal{H}\\\
|T|=n-i\cdot\sqrt{n}\end{subarray}}}{\leavevmode\nobreak\ \mathbb{E}[f(T)]}$

be the minimum expected cost of filling _any_ array with $i\cdot\sqrt{n}$
empty cells, and which contains a low/high number of gaps, for
$i\in\\{0,1,\dots,\sqrt{n}\\}$, respectively $i\in\\{0,1,\dots,\sqrt{n}-1\\}$.
(Note that $\mathcal{H}(\sqrt{n})$ is undefined as an empty array cannot have
a high number of gaps.)

Combining Equation 1 with Lemma 2.1 we obtain

$\displaystyle\mathcal{L}(i)$
$\displaystyle\geq\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min\\{{3}/{16}+\mathcal{L}(i-1),\,\mathcal{H}(i-1)\\},$
$\displaystyle\mathcal{H}(i)$
$\displaystyle\geq{1}/{16}+\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min\left\\{\mathcal{L}(i-1),\,\mathcal{H}(i-1)\right\\},$

with $\mathcal{L}(0)=\mathcal{H}(0)=0$. Our next Lemma, proved by induction
(see Appendix A), leads to the lower bound.

######  Lemma 2.5.

$\mathcal{L}(\sqrt{n})\in\Omega(\sqrt{n})$.

As the empty mapping $\emptyset$ is contained in $\mathcal{L}$ we have
$\mathbb{E}[f(\emptyset)]\geq\mathcal{L}(\sqrt{n})\in\Omega(\sqrt{n})$. Yao’s
minmax principle [21, Prop. 2.6] implies the lower bound on the expected cost
of randomized algorithms for a worst-case input.

##  3 Competitiveness for online TSP

We now consider the generalization of online sorting that we call _online
TSP_. Given a sequence $X=(x_{1},\dots,x_{n})\in S^{n}$ for some metric space
$S$, and a bijection $f\colon[n]\rightarrow[n]$, and $A[i]=x_{f(i)}$, let
$\mathtt{D}_{f}(X)=\sum_{i=1}^{n-1}{d(A[i+1],A[i])}$. Here, $d(\cdot,\cdot)$
is a metric over $S$. As before,
$\mathtt{OPT}(X)=\min_{f}{\mathtt{D}_{f}(X)}$, i.e., the _offline optimum_ ,
and $\mathcal{A}(X)$ is the cost $\mathtt{D}_{f}(X)$ for a function $f$
constructed by an online algorithm $\mathcal{A}$ on input sequence $X$. We
define $\mathtt{C}_{\mathcal{A}}$ and $\mathtt{C}$ as before.

Our main interest is in the case $S=\mathbb{R}^{d}$, and particularly $d=2$,
with $d(\cdot,\cdot)$ the Euclidean distance. As a tool in the study of the
Euclidean case, we first look at a simpler, _uniform metric_ problem in § 3.1,
showing a tight $\Theta(\log{n})$ bound on the competitive ratio. Then, in §
3.2 we study the Euclidean $\mathbb{R}^{2}$ and $\mathbb{R}^{d}$ cases. As the
uniform metric case is natural in itself, we revisit it in § 3.3 in the
setting where the array size is larger than $n$.

###  3.1 Uniform metric

Let $S$ be an arbitrary discrete set and consider the distance function
$d(x,y)=0$ if $x=y$ and $d(x,y)=1$ otherwise. Let $K=K(X)$ denote the number
of distinct entries in the input sequence $X$, i.e.,
$K=|\\{x_{1},\dots,x_{n}\\}|$. We give instance-specific bounds on the cost in
terms of $K$ and $n$. The following claim is obvious.

######  Claim 3.

$\mathtt{OPT}(X)=K-1$.

Next, we give a bound on the online cost and show that it is asymptotically
optimal.

######  Claim 4.

There is an online algorithm $\mathcal{A}$ with cost $\mathcal{A}(X)\leq
K\log_{2}{n}.$

######  Claim 5.

For every (possibly randomized) algorithm $\mathcal{A}$ and all $K\geq 3$,
there is an input distribution $X$ with $K=K(X)$ such that
$\mathbb{E}\\!\left[{\mathcal{A}(X)}\right]\in\Omega(K\log{n})$.

Note that the condition $K\geq 3$ is essential; if $K=1$, then
$\mathcal{A}(X)=\mathtt{OPT}(X)=0$ for every algorithm $\mathcal{A}$, and if
$K=2$, then there is an online algorithm $\mathcal{A}$ that achieves
$\mathcal{A}(X)=\mathtt{OPT}(X)=1$. (Place the two types of elements at the
opposite ends of the array.)

Claims 3, 4, 5 together yield the main result of this subsection.

See 1.3

######  Proof 3.1 (Proof of Claim 4).

We describe algorithm $\mathcal{A}$ (see Appendix B for an alternative),
noting that it is not required to know $K$ in advance. Assume without loss of
generality that $\\{x_{1},\dots,x_{n}\\}=\\{1,2,\dots,K\\}$. For each $j$,
with $1\leq j\leq K$, maintain a _cursor_ $c_{j}\in[n]$ indicating the array
cell where the next item $x_{i}$ is placed if it equals $j$. More precisely,
if $x_{i}=j$, then let $f({c_{j}})=i$, and move the cursor to the right:
$c_{j}=\min\\{c_{j}+1,n\\}$.

If $f(c_{j})$ is already assigned (i.e., the cell $A[c_{j}]$ is already
written), set $c_{j}$ to the mid-point of the largest empty contiguous
interval. Similarly, when $j$ is encountered the first time, then initialize
$c_{j}$ at the mid-point of the largest empty contiguous interval. Thus,
initially, $c_{x_{1}}=\lfloor{n/2}\rfloor$, i.e., place the first element at
the middle of the array.

Clearly, $\mathcal{A}$ can always place $x_{i}$ _somewhere_ , so $\mathcal{A}$
correctly terminates. It remains to prove the upper bound on the number of
unequal neighbors at the end of the process.

We model the execution of $\mathcal{A}$ as a coin-game. Consider a number of
up to $K$ _piles_ of coins. The game starts with a single pile of $n$ coins.
An adversary repeatedly performs one of two possible operations: (1) remove
one coin from an arbitrary pile, (2) split the _largest_ pile into two equal
parts. Operation (2) is only allowed when the number of piles is less than
$K$, and only for a pile of at least two coins. The game ends when all coins
have been removed.

It is easy to see that this game models the execution of $\mathcal{A}$ in the
sense that for any execution of $\mathcal{A}$ on $X$ there is an execution of
the coin-game in which the sizes of the piles correspond at each step to the
lengths of the contiguous empty intervals in the array. Moreover, the number
of consecutive unequal pairs at the end of algorithm $\mathcal{A}$ (i.e., the
cost $\mathcal{A}(X)$) is at most the number of splits (i.e., operations (2))
of the coin-game execution. It is thus sufficient to upper bound the number of
splits in _any_ execution of the coin game.

Let $n_{i}$ denote the size of a pile before its split, for the $i$-th split
operation. As $n_{i}$ is the size of the largest pile and piles can only get
smaller, the sequence $n_{i}$ is non-increasing. Suppose the $i$-th split
replaces a pile of size $t$ with two piles of size $t/2$. Then, after the
split there are at most $K-2$ piles with sizes in $[t/2,t]$ and no pile
greater than $t$. Thus, after at most $K-2$ further splits, we split a pile of
size at most $t/2$. (Possible operations (1) can only strengthen this claim,
as they make some piles smaller.) It follows that $n_{i+K}\leq n_{i}/2$ for
all $i$. As $n_{1}\leq n$, and $n_{i}\geq 1$ for all $i$, the number of splits
is at most $K\log_{2}{n}$.

######  Proof 3.2 (Proof of Claim 5).

Let $\mathcal{A}$ be an algorithm filling the items into an array $A$ of size
$n$. We present a distribution over inputs $X$ incurring cost
$\mathbb{E}\\!\left[{X}\right]\geq\Omega(K\log n)$. By Yao’s minmax principle
[21, Prop. 2.6] we thus get that every randomized algorithm has a worst-case
input of cost $\Omega(K\log n)$.

For each free cell $A[i]$ we say that $A[i]$ is _friendly_ for the two
(possibly identical) elements $y_{k}$ and $y_{l}$ that are placed closest to
the left and right of $A[i]$ in $A$. When asked to place an element $y$ into
$A$, $\mathcal{A}$ will increase the cost of the partial solution _unless_ $y$
is placed in a cell that is friendly for $y$. When placing $y$ in a cell that
is friendly for $y$, the number of friendly cells for $y$ will decrease by
one. The number of friendly cells for other elements may or may not decrease,
but no element will have more friendly cells than before the insertion of $y$.

Let $z_{1}\leq z_{2}\leq\cdots\leq z_{K}$ be the number of friendly cells for
each of the $K$ values, sorted nondecreasingly. With $n^{\prime}$ free cells
in $A$, $\sum_{i=1}^{K}z_{i}\leq 2n^{\prime}$, and hence $z_{1}\leq
2n^{\prime}/K$. Consider the median $z_{\MT@delim@Auto\floor@star{K/2}}$. As
$\sum_{i=\MT@delim@Auto\floor@star{K/2}}^{K}z_{i}\leq 2n^{\prime}$, we have
$z_{1}\leq\dots\leq
z_{\MT@delim@Auto\floor@star{K/2}}\leq\frac{2n^{\prime}}{\frac{1}{2}K}=4n^{\prime}/K$.

We now describe our input distribution, proceeding in _epochs_ : At the start
of each epoch a value $y$ is chosen uniformly at random from
$\left\\{1,\dots,K\right\\}$, and this element is presented all through the
epoch. If $K\in\left\\{3,4\right\\}$, the epoch will consist of
$2n^{\prime}/K$ copies of $y$, where $n^{\prime}$ is the number of unoccupied
cells at the start of the epoch. By the first observation above,
$\Pr\\!\left[{z_{y}\leq 2n^{\prime}/K}\right]\geq 1/K\geq 1/4$, in which case
the input forces $\mathcal{A}$ to increase the cost of the partial solution.

If $K>4$, we instead let the epoch be of length $4n^{\prime}/K$, and by the
second observation above we obtain that $\Pr\\!\left[{z_{y}\leq
4n^{\prime}/K}\right]\geq 1/2$, again increasing the cost of the partial
solution with constant probability.

To establish a lower bound for the expected cost produced by this input, it
remains to lower bound the number of epochs processed. For small $K$, the
epoch leaves $n^{\prime}\cdot\frac{K-2}{K}$ free cells for the coming epochs.
For $K>4$ the epoch leaves $n^{\prime}\cdot\frac{K-4}{K}$ free cells. Thus, in
both cases, the number of epochs is at least

$\log_{\frac{K}{K-4}}(n)=\frac{\log_{2}(n)}{\log_{2}\left(1+\frac{4}{K-4}\right)}\geq\frac{K-4}{4}\log_{2}(n)\,.$

Hence, the input will force $\mathcal{A}$ to produce a solution of expected
cost $\Omega(K\log n)$.

###  3.2 Online TSP in $\mathbb{R}^{d}$

We now proceed to the case where $S=\mathbb{R}^{d}$ and $d(\cdot,\cdot)$ is
the Euclidean distance. We start with the first new case, $d=2$. For ease of
presentation, we omit floors and ceilings in the analysis. We assume that the
input points are from the unit box $[0,1]^{2}$ and that the optimum length is
at least $1$. These assumptions can be relaxed by a similar doubling-approach
as in the proof of Claim 1.

The following result is well known [5, 17, 12] (consider, e.g., a
$\sqrt{n}\times\sqrt{n}$ uniform grid).

######  Claim 6.

For all sequences $X$ of $n$ points in $[0,1]^{2}$, we have
$\mathtt{OPT}(X)\in O(\sqrt{n})$. Moreover, there exists a sequence $X$ of $n$
poins in $[0,1]^{2}$ such that $\mathtt{OPT}(X)\in\Omega(\sqrt{n})$.

As a warm-up before our competitiveness result, we give an upper bound on the
cost of an online algorithm and we show the tightness of this bound. The
arguments extend the one-dimensional ones in a straightforward way. The proofs
of the following can be found in Appendix B.

######  Claim 7.

There is an online algorithm $\mathcal{A}$ such that $\mathcal{A}(X)\in
O(n^{2/3})$ for all $X\in[0,1]^{2}$.

######  Claim 8.

For every deterministic $\mathcal{A}$ there is an input $X$ such that
$\mathcal{A}(X)\in\Omega(n^{2/3})$.

Now we move to the study of the competitive ratio. Note that the lower bound
of Claim 2 immediately applies to our setting. Combined with Claim 7, it
follows that $\mathtt{C}\in O(n^{2/3})\cap\Omega(n^{1/2})$. In the following
we (almost) close this gap, proving the following.

######  Claim 9.

The competitive ratio of online TSP in $\mathbb{R}^{2}$ is
$O(\sqrt{n\log{n}})$.

Partition the box $[0,1]^{2}$ into $t\times t$ boxes of sizes $1/t\times 1/t$,
for $t$ to be set later. Let $K$ be the number of boxes that are _touched_ ,
i.e., that contain some input point $x_{i}$. We first need to lower bound the
optimum.

######  Lemma 3.3.

$\mathtt{OPT}(X)\geq K/4t$.

######  Proof 3.4.

If $K/4t<1$, we are done, as $\mathtt{OPT}(X)\geq 1$ by assumption. Assume
therefore $K\geq 4t$. Choose an arbitrary representative point of $X$ from
each touched box. Observe that the optimum cannot be shorter than the optimal
tour of the representatives (by triangle inequality). Among any five
consecutive vertices of the representatives-tour, two must be from non-
neighboring boxes, thus the total length of the four edges connecting these
points is at least $1/t$. It follows that at least $K/4$ edges have this
length, yielding the claim.

Now we need an algorithm that does well in terms of $K$. For any two
neighboring entries in the array we consider only whether they come from the
same box. This allows us to reduce our problem to the uniform metric case
(Claim 4).

######  Claim 10.

There is an online algorithm $\mathcal{A}$ such that $\mathcal{A}(X)\in
O(K\log{n}+n/t)$.

######  Proof 3.5.

We treat points from the same box as having the _same value_. We run the
algorithm for the uniform metric given in Claim 4, incurring a total number of
$O(K\log{n})$ differing pairs of neighbors. For these pairs we account for a
maximum possible cost of $\sqrt{2}$. All other neighboring pairs have the same
value (= come from the same box), incurring a cost of at most $O(1/t)$ each,
for a total of $O(n/t)$. This completes the proof.

Together with Lemma 3.3, this yields Claim 9. Indeed, set
$t=\sqrt{\frac{n}{\log{n}}}$. If $K\leq t$, then using $\mathtt{OPT}\geq 1$,
we have $\mathcal{A}/\mathtt{OPT}\leq\frac{K\log{n}+n/t}{1}\in
O(\sqrt{n\log{n}})$. If $K>t$, then using Lemma 3.3,
$\mathcal{A}/\mathtt{OPT}\leq\frac{K\log{n}+n/t}{K/4t}=4t\log{n}+4n/K\in
O(\sqrt{n\log{n}})$.

Online TSP in $\mathbb{R}^{d}$. We now extend the bound on the competitive
ratio (Claim 9) to the higher dimensional case, also considering the
dependence on $d$, leading to the claimed result.

See 1.2

Analogously to Claim 6, we first state an absolute bound on the optimal TSP
cost in $d$ dimensions, treating $d$ as a constant [5, 17, 12].

######  Claim 11.

For all sets $X$ of $n$ points in $[0,1]^{d}$, we have $\mathtt{OPT}(X)\in
O(n^{1-1/d})$. Moreover, there exists a set $X$ of $n$ poins in $[0,1]^{d}$
such that $\mathtt{OPT}(X)\in\Omega(n^{1-1/d})$.

A straightforward generalization of Claims 7 and 8 yields (for all constant
$d$):

######  Claim 12.

There is an online algorithm $\mathcal{A}$ for online TSP in $\mathbb{R}^{d}$
such that $\mathcal{A}(X)\in O(n^{1-\frac{1}{d+1}})$ for all $X$. For every
deterministic algorithm $\mathcal{A}$ there is an input $X$ such that
$\mathcal{A}(X)\in\Omega(n^{1-\frac{1}{d+1}})$.

######  Proof 3.6 (Proof of Theorem 1.2.).

We follow the proof of Claim 9, with minor changes. We assume the input to
come from the $d$-dimensional unit box $[0,1]^{d}$. We partition this box into
$t^{d}$ boxes of sizes $(1/t)^{d}$. When adapting Lemma 3.3, we have to
consider $2^{d}$ (instead of $4$) consecutive tour edges, thus obtaining
$\mathtt{OPT}(X)\geq\frac{K}{2^{d}t}$. When adapting Claim 10, our upper bound
increases by a factor of $\sqrt{d}$, the distance between antipodal vertices
of a unit $d$-cube, replacing the implicit $\sqrt{2}$ in the earlier bound.
Thus, when bounding the competitive ratio, we incur an overall factor of
$\sqrt{d}\cdot 2^{d}$, yielding the result.

###  3.3 Uniform metric with a larger array

We study the problem of placing $n$ elements $\\{1,\dots,K\\}$ into an array
of size $\MT@delim@Auto\ceil@star{\gamma n}$ for a fixed $\gamma>1$. The
algorithm and distribution from Claims 4 and 5 can be reused in this setting,
stopping either process after the insertion of the first $n$ elements.

######  Claim 13.

For every algorithm $\mathcal{A}$ and any number $K\geq 3$ of input values,
there is an input distribution $X$ such that
$\mathbb{E}\\!\left[{\mathcal{A}(X)}\right]\in\Omega(K\cdot(1+\log(\gamma/(\gamma-1))))$.

######  Claim 14.

There is an online algorithm $\mathcal{A}$ with cost $\mathcal{A}(X)\in
O(K\cdot(1+\log(\gamma/(\gamma-1)))).$

The two claims together imply Theorem 1.4. We defer their proofs to Section
B.1. They rely on similar arguments as the proofs of the claims mentioned
above, with a refined argument for counting the number of epochs/moves
performed.

##  4 Competitiveness for stochastic online sorting

In this section, we prove Theorem 1.5 and Theorem 1.6 (§ 4.1). See 1.5

We start by describing the general design of the algorithm from Theorem 1.5
and showing some fundamental properties. We then describe a recursive
algorithm and give the parameterizations that achieve the desired competitive
cost.

The general design. We let $\alpha$ and $\beta$ denote two parameters in
$(0,1)$ which we will set later. We decompose the array $A$ of $n$ cells as
such: the first $N=n-n^{\beta}$ cells are divided into $M=n^{\alpha}$
consecutive sub-arrays $A_{1},\ldots,A_{n^{\alpha}}$, and the remaining
$n^{\beta}$ cells (at the end of the array) form one single subarray denoted
by $B$. We refer to each of the sub-arrays $A_{i}$ as a _bucket_ and to $B$ as
the _backyard_. We note that each bucket $A_{i}$ can hold $C=N/M$ elements,
which we refer to as the _capacity_ of the bucket.

We use the values of the elements to hash them into the array. Namely, for an
element $x\in(0,1)$, we define $h\colon(0,1]\rightarrow\\{1,\ldots,M\\}$ by
setting $h(x)=\MT@delim@Auto\ceil@star{x\cdot M}$. In other words, the
elements in the interval $(0,1/M]$ will all hash to bucket $1$, elements in
the interval $(1/M,2/M]$ will hash to bucket $2$, etc. Since the elements are
chosen independently and uniformly at random from $(0,1]$, we get that $h$
assigns the elements independently and uniformly at random into the $M$
buckets.666We assume that there is no element of value $0$. The probability of
this happening is $0$.

$\textsf{SortUnif}_{1}(A,n)$: the first algorithm. Let $\textsf{SortDet}(A,n)$
denote the deterministic algorithm from [1]. We now define the algorithm
$\textsf{SortUnif}_{1}(A,n)$ as such: upon receiving $x$, it checks if the
bucket $A_{h(x)}$ has any empty cells. If so, it forwards $x$ to
$\textsf{SortDet}(A_{h(x)},C)$. Otherwise, it forwards $x$ to
$\textsf{SortDet}(B,n^{\beta})$ (and we say that the corresponding bucket is
_full_).

We first prove that $\textsf{SortUnif}_{1}(A,n)$ successfully places all items
with high probability. Note that this is not always guaranteed: it could
happen that both the bucket and the backyard are full (before we have managed
to place all the $n$ elements). If this happens, then among all $n$ elements,
strictly less than $C$ hash into some bucket. We call this event a _failure_
and show the following by employing a Chernoff bound (Appendix C):

######  Claim 15.

Given any $c>0$, if $\beta\geq\frac{1}{2}\cdot\left(1+\alpha+\frac{\ln\ln
n+\ln(2(c+1))}{\ln n}\right)$, then $\textsf{SortUnif}_{1}(A,n)$ fails with
probability at most $1/n^{c}$.

We now bound the cost of $\textsf{SortUnif}_{1}(A,n)$:

######  Claim 16.

If $\textsf{SortUnif}(A,n)$ does not fail, then its cost is at most
$O(\sqrt{C}+n^{\beta/2})$.

######  Proof 4.1.

Since each bucket receives at least $C$ elements, the cost of placing elements
inside bucket $A_{1}$ is given by the cost of $\textsf{SortDet}(A_{1},C)$ on
elements from $(0,1/M)$. We bound this by $O(\sqrt{C}\cdot 1/M]$. For the
remaining buckets, the elements are drawn from $(i/M,(i+1)/M)]$. This is
equivalent to sorting elements from $(0,1/M]$, and so their cost is the same
as that of $A_{1}$. Therefore, in total, the cost from each individual bucket
is $O(\sqrt{C})$. In addition, we also have the cost from crossing from one
bucket to the next. This is at most $2/M$, since the maximum difference
between elements from consecutive buckets is at most $2/M$. Since there are
$M$ buckets, this amounts to a cost of at most $2$. The cost of crossing from
bucket $A_{M}$ to the backyard is $1$. Finally, the cost in the backyard is
$O(n^{\beta/2})$, since it employs $\textsf{SortDet}(B,n^{\beta})$ on elements
from $(0,1)$.

We instantiate $\alpha$ and $\beta$ such that we get the following (proof in
Appendix C):

######  Lemma 4.2.

Given any $c>0$, $\textsf{SortUnif}_{1}(A,n)$ has cost at most
$O(n^{1/3}\cdot\ln^{1/6}n\cdot(2(c+1))^{1/6})$ with probability at least
$1-1/n^{c}$.

$\textsf{SortUnif}_{k}$: recursing on the buckets. We take advantage of the
fact that within each bucket, the elements are chosen uniformly at random.
That is, we can apply the same strategy recursively inside the bucket. We get
a series of algorithms $\textsf{SortUnif}_{k}$ for $k\geq 2$. In
$\textsf{SortUnif}_{k}$, we let $\alpha$ and $\beta$ be defined as in
$\textsf{SortUnif}_{1}$. When we see an element $x$ with $h(x)=i$, if its
bucket $A_{i}$ is not full, we place $(xM-i+1)$ using
$\textsf{SortUnif}_{k-1}(A_{h(x)},C)$. Note that we have already conditioned
on the fact that $\MT@delim@Auto\ceil@star{x\cdot M}=i$. In this case,
$(xM-i+1)$ becomes uniformly distributed in $(0,1)$. If $A_{i}$ is full, we
place $x$ in the backyard according to $\textsf{SortDet}(B,n^{\beta})$.

Note that there are now several causes for failure: either some bucket $A_{i}$
is not full, or one of the algorithms inside the bucket fails. We bound the
probability of either of these happening as follows, proving the claim by
induction over $k$ (Appendix C):

######  Lemma 4.3.

Given any $c>0$, $\textsf{SortUnif}_{k}(A,n)$ has cost at most

$O\left(n^{1/f_{k}}\cdot\ln^{1/4}n\cdot(2(c+1))^{B_{k}}\right)$

with probability at least $1-2/n^{c}$, where $f_{k}=4-1/2^{k-1}$ and
$B_{k}=k/4$.

Setting $c=1$ and $k=\log_{2}\left(2/(4+\ln n-\sqrt{\ln^{2}n+8\ln n})\right)$
yields the bounds claimed in Theorem 1.5; the details are given in Appendix C.

###  4.1 Stochastic online sorting in larger arrays

See 1.6

The algorithm. Define $\alpha=(\gamma-1)/10$ and $\beta=\gamma-\alpha$ such
that array $A$ has size $(\beta+\alpha)n$. We will refer to the final $\alpha
n$ cells of $A$ as the _buffer_. The first $\beta n$ cells we consider to
correspond to the interval $[0,1)$. More specifically, cell $A[i]$ represents
the interval $\left[\frac{i}{\beta n},\,\frac{i+1}{\beta n}\right)$.

Let $h\colon[0,1)\to\left\\{0,\beta n-1\right\\}$ be the function which maps
values $x\in[0,1)$ to the index of the corresponding cell:
$h(x)=\MT@delim@Auto\floor@star{\frac{x}{\beta n}}$. Our algorithm
$\mathcal{A}$ inserts each value $x$ into $A[h(x)]$ if the cell is available,
and otherwise into the _first_ available cell following $h(x)$, possibly
wrapping around from $A[\gamma n-1]$ to $A[0]$ (although, as we argue in
Section C.1, this is unlikely). In other words, $x$ is inserted into the cell
$A[h(x)+i\mod\gamma n]$ where $i$ is the smallest non-negative integer such
that the specified cell is available.

Counting steps. As the values are drawn independently and uniformly from
$[0,1)$, the indices $h(x)$ are also independently and uniformly distributed
in $\left\\{0,\dots,\beta n-1\right\\}$. The algorithm thus mirrors the scheme
of linear probing commonly used for implementing hash tables. In linear
probing each key $x$ that is to be added to the table (and which is generally
not assumed to come from a known distribution) is hashed to an index of the
array, and $x$ is inserted into the first following free cell.

When implementing a hash table, one is interested in analyzing the _speed_ of
insertions, which for linear probing corresponds to the number of cells that
are probed before a free cell is found. Although speed is not a concern for
our online algorithm, we will nonetheless show that the number of steps
performed is an important measure for bounding the cost of our solution.
Formally, let $s(k)$ be the number of steps performed when inserting the
$k$-th value $x_{k}$ of the input. If $A[h(x_{k})]$ is free, then $s(k)=1$;
otherwise $s(k)=i+1$, when $x_{k}$ is inserted into cell
$A[h(x_{k})+i\mod\gamma n]$.

Now consider the linear probing process $\mathcal{A}_{LP}$ inserting $n$
elements into a table $T$ of size $\beta n$ (that is, without the buffer
space). Analogously to $s(i)$ we let $s_{LP}(i)$ be the number of steps
performed by $\mathcal{A}_{LP}$ when inserting the $i$-th element. We couple
the processes $\mathcal{A}$ and $\mathcal{A}_{LP}$ so that they encounter the
same stream of indices $h(x_{1}),h(x_{2}),\ldots,h(x_{n})$ during execution.
We then have $s(i)\leq s_{LP}(i)$. Indeed, the only difference between the
processes is that $\mathcal{A}$ has an extra $\alpha n$ cells of buffer space
to prevent wraparound at the end of $A$. More generally, we thus have
$\mathbb{E}\\!\left[{s(i)}\right]\leq\mathbb{E}\\!\left[{s_{LP}(i)}\right]$.
Combining the pieces we get that:

######  Claim 17.

$\mathbb{E}\\!\left[{\mathcal{A}(X)}\right]\leq O\left(1+\frac{1}{\beta
n}\sum_{i=1}^{n}\mathbb{E}\\!\left[{s(i)}\right]\right).$

The proof can be found in Section C.1. We then invoke the following classic
result by Knuth [18] to bound $\sum_{i}\mathbb{E}\\!\left[{s_{LP}(i)}\right]$:

######  Theorem 4.4 ([18]).

Consider the process of inserting $(1-\varepsilon)m$ elements into an array of
size $m$ by linear probing. When hash values are assigned uniformly and
independently,

$\sum_{i=1}^{(1-\varepsilon)m}\mathbb{E}\\!\left[{s_{LP}(i)}\right]\in
O\left((1-\varepsilon)m\cdot\frac{1}{\varepsilon}\right)\,.$

To apply Theorem 4.4, set $m=\beta n$ and $\varepsilon=(\beta-1)/\beta$ such
that $(1-\varepsilon)m=n$, and thus
$\sum_{i=1}^{n}\mathbb{E}\\!\left[{s(i)}\right]\leq\sum_{i=1}^{n}\mathbb{E}\\!\left[{s_{LP}(i)}\right]\in
O\left(n\cdot\left(\frac{\beta}{\beta-1}\right)\right)$. As
$\beta-1=\frac{9}{10}\cdot(\gamma-1)$, we have
$\mathbb{E}\\!\left[{\mathcal{A}(X)}\right]\in
O\left(1+\frac{1}{\beta}\cdot\frac{\beta}{\beta-1}\right)\subseteq
O\left(1+\frac{1}{\gamma-1}\right)$, proving Theorem 1.6.∎

##  5 Conclusion and open questions

In this paper, we studied the online sorting problem in some of its variants.
Several questions and directions to further study remain, we mention those
that we find most interesting.

Online sorting of reals. For large arrays ($m=\MT@delim@Auto\ceil@star{\gamma
n}$, for $\gamma>1$) significant gaps remain between the upper and lower
bounds on the competitive ratio of online sorting (see [1]).

In a different direction, consider online sorting and _online list labeling_ ,
mentioned in § 1. These can be seen as two extremes of an “error vs. recourse”
trade-off: online sorting allows no recourse, while list labeling allows no
error. Achieving a smooth trade-off between the two optimization problems by
some hybrid approach is an intriguing possibility.

Stochastic and other models. In the stochastic setting of online sorting, we
could improve upon the worst-case bound, but the obtained ratio (Theorem 1.5)
is likely not optimal; we are not aware of nontrivial lower bounds. For
stochastic online sorting with large arrays (Theorem 1.6), a matching lower
bound is likewise missing. We restricted our study to uniform distribution
over an interval; extending the results to other distributions remains open.

Other models that go beyond the worst-case assumption could yield further
insight; we mention two possible models: (1) online sorting _with advice_
(e.g., from a machine learning model): suppose that each input item comes with
a possibly unreliable estimate of its rank in the optimal (sorted) sequence;
what is the best way to make use of this advice? (2) online sorting _with
partially sorted input_ : for instance, suppose that the _input cost_
$\sum_{i=1}^{n-1}{|x_{i+1}-x_{i}|}$ is small. What is the best guarantee for
the online sorting cost in this case?

Online TSP in various metrics. For online TSP in $\mathbb{R}^{d}$, for fixed
$d$, a small gap remains between the lower bound $\Omega(\sqrt{n})$ and upper
bound $O(\sqrt{n\log{n}})$ on the competitive ratio (Theorem 1.2). The
dependence on $d$ (when $d\in\omega(1)$) is not known to be optimal. Online
TSP in $\mathbb{R}^{d}$ with large array, and/or with stochastic input are
also interesting directions.

Some non-Euclidean metrics pose natural questions, e.g., $L_{0}$ or
$L_{\infty}$ in $\mathbb{R}^{d}$, or tree- or doubling metrics. More broadly,
is the optimal competitive ratio $O(\sqrt{n})$ for arbitrary metrics?

## References

  * [1] Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta, and Linda Kleist.  Online sorting and translational packing of convex polygons.  In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 1806–1833. SIAM, 2023.  URL: https://doi.org/10.1137/1.9781611977554.ch69, doi:10.1137/1.9781611977554.CH69.
  * [2] Yuriy Arbitman, Moni Naor, and Gil Segev.  Backyard cuckoo hashing: Constant worst-case operations with a succinct representation.  In 2010 IEEE 51st Annual symposium on foundations of computer science, pages 787–796. IEEE, 2010.
  * [3] Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, and Maurizio Talamo.  Algorithms for the on-line travelling salesman 1.  Algorithmica, 29:560–581, 2001.
  * [4] Eric Balkanski, Yuri Faenza, and Noémie Périvier.  The power of greedy for online minimum cost matching on the line.  In Proceedings of the 24th ACM Conference on Economics and Computation, pages 185–205, 2023.
  * [5] Jillian Beardwood, J. H. Halton, and J. M. Hammersley.  The shortest path through many points.  Mathematical Proceedings of the Cambridge Philosophical Society, 55(4):299–327, 1959.  doi:10.1017/S0305004100034095.
  * [6] Michael A Bender, Richard Cole, Erik D Demaine, Martin Farach-Colton, and Jack Zito.  Two simplified algorithms for maintaining order in a list.  In European Symposium on Algorithms, pages 152–164. Springer, 2002\.
  * [7] Michael A Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole Wein.  Online list labeling: Breaking the log 2 n barrier.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 980–990. IEEE, 2022.
  * [8] Michael A. Bender, Martin Farach-Colton, John Kuszmaul, William Kuszmaul, and Mingmou Liu.  On the optimal time/space tradeoff for hash tables.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 \- 24, 2022, pages 1284–1297. ACM, 2022.  doi:10.1145/3519935.3519969.
  * [9] Antje Bjelde, Jan Hackfeld, Yann Disser, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Miriam Schlöter, Kevin Schewior, and Leen Stougie.  Tight bounds for online tsp on the line.  ACM Transactions on Algorithms (TALG), 17(1):1–58, 2020.
  * [10] Allan Borodin and Ran El-Yaniv.  Online computation and competitive analysis.  Cambridge University Press, 1998.
  * [11] Paul F Dietz.  Maintaining order in a linked list.  In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 122–127, 1982.
  * [12] L. Few.  The shortest path and the shortest road through n points.  Mathematika, 2(2):141–144, 1955.  doi:10.1112/S0025579300000784.
  * [13] Amos Fiat and Gerhard J. Woeginger.  On-line scheduling on a single machine: Minimizing the total completion time.  Acta Informatica, 36(4):287–293, 1999.  URL: https://doi.org/10.1007/s002360050162, doi:10.1007/S002360050162.
  * [14] Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc.  Stochastic online metric matching.  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2019.
  * [15] Anupam Gupta and Kevin Lewi.  The online metric matching problem for doubling metrics.  In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I 39, pages 424–435. Springer, 2012.
  * [16] Alon Itai, Alan G Konheim, and Michael Rodeh.  A sparse table implementation of priority queues.  In International Colloquium on Automata, Languages, and Programming, pages 417–431. Springer, 1981.
  * [17] Howard J. Karloff.  How long can a euclidean traveling salesman tour be?  SIAM J. Discret. Math., 2(1):91–99, 1989.  doi:10.1137/0402010.
  * [18] Donald E. Knuth.  Notes on open addressing.  Unpublished memorandum. See http://citeseer.ist.psu.edu/knuth63notes.html, 1963.
  * [19] Donald E. Knuth.  The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching.  Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998\.
  * [20] Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese.  The power of recourse for online mst and tsp.  In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I 39, pages 689–700. Springer, 2012.
  * [21] Rajeev Motwani and Prabhakar Raghavan.  Randomized algorithms.  In Mikhail J. Atallah, editor, Algorithms and Theory of Computation Handbook, Chapman & Hall/CRC Applied Algorithms and Data Structures series. CRC Press, 1999.  URL: https://doi.org/10.1201/9781420049503-c16, doi:10.1201/9781420049503-C16.
  * [22] Christos H Papadimitriou.  The euclidean travelling salesman problem is np-complete.  Theoretical computer science, 4(3):237–244, 1977.
  * [23] Kirk Pruhs, Jirí Sgall, and Eric Torng.  Online scheduling.  In Joseph Y.-T. Leung, editor, Handbook of Scheduling - Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC, 2004.  URL: http://www.crcnetbase.com/doi/abs/10.1201/9780203489802.ch15, doi:10.1201/9780203489802.CH15.
  * [24] Sharath Raghvendra.  Optimal analysis of an online algorithm for the bipartite matching problem on a line.  In 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [25] Tim Roughgarden, editor.  Beyond the Worst-Case Analysis of Algorithms.  Cambridge University Press, 2020.  doi:10.1017/9781108637435.
  * [26] Michael Saks.  Online labeling: Algorithms, lower bounds and open questions.  In International Computer Science Symposium in Russia, pages 23–28. Springer, 2018.

##  Appendix A Proofs from § 2

See 1

######  Proof A.1.

Our task is to place $n$ values $x_{1},\dots,x_{n}\in\mathbb{R}$ bijectively
into the array cells $A[1]$, $\dots$, $A[n]$. We revisit and extend the
algorithm from [1]. The main obstacle is that in [1] it can be assumed that
$\mathtt{OPT}=1$. In our case,
$\mathtt{OPT}=\max_{i}{\\{x_{i}\\}}-\min_{i}{\\{x_{i}\\}}$; as this quantity
is not known until the end, we estimate it based on the available data.

For ease of presentation assume that $x_{1}=0$. This is without loss of
generality as we can simply transform $x_{i}$ to $x_{i}-x_{1}$ for all
$i=1,\dots,n$ and the costs of both offline and online solutions are
unaffected.

Start by reading $x_{1},x_{2}$ and placing them arbitrarily (this incurs a
cost of at most $2\mathtt{OPT}$), and set
$q=\lceil\log_{2}{|x_{2}-x_{1}|}\rceil=\lceil\log_{2}{|x_{2}|}\rceil$ (as we
assumed $x_{1}=0$). Throughout the algorithm we maintain $q$ so that the input
values seen so far are in the interval $J=[-2^{q},2^{q}]$. This clearly holds
after reading $x_{2}$ . For simplicity, assume first that
$x_{3},\dots,x_{n}\in J$, and $q$ does not need to be updated.

Let $N_{1}=\lfloor\sqrt{n}\rfloor$ and $N_{2}=2N_{1}$. Partition the interval
$J$ into $N_{1}$ equal-size subintervals $J_{1},\dots,J_{N_{1}}$, called
“boxes”, and partition the array $A$ into $N_{2}$ equal-size subarrays
$A_{1},\dots,A_{N_{2}}$, called “blocks” (as $n$ is generally not divisible by
$N_{2}$, we allow one block to be smaller).

Whenever a value $x_{i}\in J_{k}$ is received, if it is the first value from
box $J_{k}$, then we assign $J_{k}$ to a yet unassigned (empty) block $A_{t}$;
we place $x_{i}$ in the leftmost cell of $A_{t}$ and continue placing future
values from $J_{k}$ into $A_{t}$ (left-to-right). If the block $A_{t}$ of
$J_{k}$ is full, we assign a new empty block to $J_{k}$.

If we run out of empty blocks, we must have processed at least $n/2$ values;
to see this, observe that of the $N_{2}=2N_{1}$ blocks, at most $N_{1}-1$ are
non-full, the rest have been filled. From this point on, we treat the
remaining $n^{\prime}\leq n/2$ empty cells of $A$ as a virtual (contiguous)
array $A^{\prime}$, recursively placing the remaining $n^{\prime}$ values into
$A^{\prime}$ by the same strategy (we restart $\mathcal{A}$ on $A^{\prime}$,
without the intitialization of $q$, i.e., we keep the current values of $q$
and $J$).

The total cost $t(n)$ of $\mathcal{A}$ is at most

$t(n)\leq t(n^{\prime})+2^{q+1}\cdot\frac{n}{N_{1}}+2^{q^{*}+1}\cdot 2N_{2}.$

The first term is the remaining cost of placing $n^{\prime}$ values into a
contiguous array of size $n^{\prime}$.

The second term is the cost due to at most $n$ values already placed within
full blocks. (As these come from one of the $N_{1}$ boxes of $J$ and $|J|\leq
2^{q+1}$, the bound follows.)

The third term is the cost due to boundaries between blocks, and “at the
interface” with the recursive call, i.e., at the margins of incomplete blocks.
(This term thus captures the cost of “pretending” $A^{\prime}$ to be
contiguous.) Here $2^{q^{*}+1}$ is an upper bound on the size of $J$
throughout the entire execution of $\mathcal{A}$ (including future points),
i.e.,
$q^{*}=\lceil\log_{2}{(\max_{i}{(x_{i})}-\min_{i}{(x_{i})})}\rceil=\MT@delim@Auto\ceil@star{\log_{2}{\mathtt{OPT}}}$,
and $q\leq q^{*}$.

We have $t(n)\leq t(n/2)+\mathtt{OPT}\cdot O(\sqrt{n})$, which resolves to
$t(n)\in\mathtt{OPT}\cdot O(\sqrt{n})$. Notice that $\mathtt{OPT}$ is the
_global optimum_ of the problem, not the optimum in the current recursive
call.

Suppose now that we receive a point $x_{i}\notin J$. We update

$q=\lceil\log_{2}{(\max_{k\leq i}{(x_{k})}-\min_{k\leq i}{(x_{k})})}\rceil$

and $J=[-2^{q},2^{q}]$. Note that the value of $q$ increased, and all values
$x_{1},\dots,x_{i}$ seen so far are also contained in the current $J$. We then
split $J$ into new boxes $J^{\prime}_{1},\dots,J^{\prime}_{N_{1}}$ (without
changing $N_{1}$ or $N_{2}$). The blocks $A_{1},\dots,A_{N_{2}}$ remain, and
if some old box $J_{i}$ was assigned to a block $A_{j}$, then we assign the
corresponding new box $J^{\prime}_{i}$ to $A_{j}$. With these changes, we
continue with the algorithm.

Observe that at the margin of every non-filled block we may end up with
neighbors not from the same box (i.e., one is from the old, one is from the
new). Thus, their distance may be up to $|J|=2^{q+1}$, so we incur an
additional cost of at most $2^{q+1}\cdot N_{1}\leq 2^{q+1}\cdot\sqrt{n}$.

We may incur such an extra cost several times during the execution, but always
for a different integer $q\leq q^{\star}$. As
$2^{q^{\star}-1}\leq\mathtt{OPT}\leq 2^{q^{\star}+1}$, the total extra cost is
at most $\sum_{q\leq q^{\star}}{2^{q+1}\cdot\sqrt{n}}\in\mathtt{OPT}\cdot
O(\sqrt{n})$, and the overall bound is unaffected.

See 2.5

######  Proof A.2.

Proceed by induction on $i$. For all $i^{\prime}\in\\{0,\dots,i-1\\}$ assume

$\displaystyle\mathcal{H}(i^{\prime})$
$\displaystyle\geq\left(1-\frac{1}{\sqrt{n}}\right)^{i^{\prime}}\cdot\frac{i^{\prime}}{32},$
$\displaystyle\mathcal{L}(i^{\prime})$
$\displaystyle\geq\left(1-\frac{1}{\sqrt{n}}\right)^{i^{\prime}}\cdot\frac{i^{\prime}-1}{32}.$

Then

$\displaystyle\mathcal{H}(i)$
$\displaystyle\geq\frac{1}{16}+\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min\\{\mathcal{L}(i-1),\,\mathcal{H}(i-1)\\}$
$\displaystyle\geq\frac{1}{16}+\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min\left\\{\left(1-\frac{1}{\sqrt{n}}\right)^{i-1}\cdot\frac{i-2}{32},\,\left(1-\frac{1}{\sqrt{n}}\right)^{i-1}\cdot\frac{i-1}{32}\right\\}$
$\displaystyle\geq\left(1-\frac{1}{\sqrt{n}}\right)^{i}\cdot\frac{i}{32},$

and

$\displaystyle\mathcal{L}(i)$
$\displaystyle\geq\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min\left\\{\frac{3}{16}+\mathcal{L}(i-1),\,\mathcal{H}(i-1)\right\\}$
$\displaystyle\geq\left(1-\frac{1}{\sqrt{n}}\right)\cdot\min\left\\{\frac{3}{16}+\left(1-\frac{1}{\sqrt{n}}\right)^{i-1}\cdot\frac{i-2}{32},\,\left(1-\frac{1}{\sqrt{n}}\right)^{i-1}\cdot\frac{i-1}{32}\right\\}$
$\displaystyle=\min\left\\{\left(1-\frac{1}{\sqrt{n}}\right)\cdot\frac{3}{16}+\left(1-\frac{1}{\sqrt{n}}\right)^{i}\cdot\frac{i-2}{32},\,\left(1-\frac{1}{\sqrt{n}}\right)^{i}\cdot\frac{i-1}{32}\right\\}$
$\displaystyle\geq\left(1-\frac{1}{\sqrt{n}}\right)^{i}\cdot\frac{i-1}{32}.$

Finally, note that $(1-\frac{1}{\sqrt{n}})^{\sqrt{n}}\geq 0.3$ for $n\geq 10$,
proving the claim.

##  Appendix B Proofs from § 3

#### An alternative algorithm for Claim 4.

We now present a different algorithm, resembling the one from [1] and the one
from the proof of Claim 1. If $K$ is known, then we can proceed in a
straightforward way: Partition the array into $2K$ blocks, assign individual
values to blocks, and when we run out of free blocks, recurse on the remaining
free space. We get a cost of $t(n)=O(K)+t(n/2)$, yielding $t(n)\in
O(K\log{n})$. Here the $O(K)$ term accounts for both the boundaries between
blocks and the interface with the recursive call.

We can handle the case of unknown $K$ by a doubling strategy, similar to the
proof of Claim 1. Namely, start with $K=2$, and run the above algorithm. When
a new element arrives that increases the number of different values seen to
$K+1$, then set $K$ to $2K$, and split each block in the current recursive
level into two equal parts. A full block will be replaced by two full blocks,
an empty block will be replaced by two empty blocks. In both cases, there is
no additional cost.

A partially filled block will be replaced either by (1) a full block and an
empty block, or (2) a full block and a partially filled block, or (3) a
partially filled block and an empty block. In either case, if the block was
assigned to a value $t$, then, if there is a resulting partially filled block,
then it will continue to be filled with values $t$. Thus there is no incurred
cost that is not accounted for already elsewhere, and the bound of
$O(K\log{n})$ holds.

See 7

######  Proof B.1.

The algorithm closely follows the online sorting algorithm of [1] and the
extension in Claim 1.

Divide the box $[0,1]^{2}$ into $n^{1/3}\times n^{1/3}$ _boxes_ of sizes
$n^{-1/3}\times n^{-1/3}$. Divide the array of size $n$ into $2n^{2/3}$ equal
size _blocks_. When a point arrives in a given box $B$, assign $B$ to a
previously unassigned block $J$, and place points from $B$ into $J$ (in
arrival order, left-to-right). If $J$ is full, assign a new block to $B$. If
no more new blocks are available, re-use the empty space by treating it as if
it were contiguous, and recursively assign blocks for the remaining (at most)
$n/2$ input points.

The total cost can be bounded as $t(n)\leq O(n^{2/3})+t(n/2)\in O(n^{2/3})$,
where we accounted for the at most $O(n^{-1/3})$ distance between any two
neighbors, and the at most $O(1)$ distance between the $O(n^{2/3})$ block-
boundaries and boundaries at the interface between the first call and the
recursive call.

See 8

######  Proof B.2.

We adapt the lower bound strategy for online sorting from [1], with the
$n^{2/3}$ allowed input points being the grid points of the $n^{1/3}\times
n^{1/3}$ uniform grid spanning $[0,1]^{2}$. We present the adversary strategy
against deterministic algorithms; a randomized oblivious adversary can be
obtained using techniques similar to those in § 2.

In the first phase, as long as there is a grid point that does not appear in
the array with an empty neighbor, output that point as the next input item. If
all grid points appear with an empty neighbor, then move to phase two, and
output $(0,0)$ points until the end. In the first phase each input item incurs
cost at least $\Omega{(n^{-1/3})}$, thus, if we remain in the first phase
until the end, then the total cost is $\Omega(n\cdot
n^{-1/3})=\Omega{(n^{2/3})}$. If we move to the second phase, then the cost is
at least

$\sum_{1\leq i,j\leq n^{1/3}}{\sqrt{i\cdot n^{-1/3}+j\cdot n^{-1/3}}},$

likewise yielding $\Omega{(n^{2/3})}$.

###  B.1 Proofs from § 3.3

See 13

######  Proof B.3.

We start by introducing one copy of each element $\\{1,\dots,K\\}$,
immediately causing a cost of $K-1$. Then, we proceed as in the proof of Claim
5, choosing a type uniformly at random. Assume $K\geq 5$. With $m^{\prime}$
free cells left in the array we repeat the chosen element $4m^{\prime}/K$
times. By the arguments presented in the proof of Claim 5, this increases the
cost of the partial solution with probability at least $1/2$. Next, a new
element is chosen, and the process is repeated with $m^{\prime}(1-4/K)$ free
cells left in the array.

The question now is how many times we can repeat this procedure before having
inserted $n$ elements. Watching the process in reverse, it is seen that with
$m^{\prime}$ cells currently free, we have caused an increase in cost (with
probability 1/2) during the previous $Km^{\prime}/(K-4)$ insertions. The
process is stopped when $m^{\prime}=(\gamma-1)n$, and started at
$m^{\prime}=\gamma n-K$. Hence we can repeat the process

$\displaystyle\log_{\frac{K}{K-4}}\left(\frac{\gamma n-K}{(\gamma-1)n}\right)$
$\displaystyle=\frac{\log_{2}\left(\frac{\gamma}{(\gamma-1)}-\frac{K}{(\gamma-1)n}\right)}{\log_{2}\left(\frac{K}{K-4}\right)}$
$\displaystyle\geq\frac{K-4}{4}\cdot\log_{2}\left(\frac{\gamma}{(\gamma-1)}-\frac{K}{(\gamma-1)n}\right)$
$\displaystyle\geq\Omega\left(K\cdot\log\left(\frac{\gamma}{\gamma-1}\right)\right)$

times. Thus the expected cost of $\mathcal{A}(X)$ will be
$K-1+1/2\cdot\Omega(K\cdot\log(\gamma/(\gamma-1)))$.

The case $K\in\left\\{3,4\right\\}$ is lifted from the proof of Claim 5 in the
same way: Letting each round be of length $m^{\prime}/K$, rounds will cause an
increase in cost with probability at least $1/K\geq 1/4$, and we can execute
$\Omega(K\cdot\log(\gamma/(\gamma-1)))$ rounds.

See 14

######  Proof B.4.

We reuse the algorithm and coin-game from the proof of Claim 4, with the
modification that the game starts with $\gamma n$ coins in a single pile and
ends when $(\gamma-1)n$ coins are left. Generalizing the observation from the
proof of Claim 4, we observe that if we at some point have $c$ piles each of
size at most $t$, then all piles will be of size at most $t/2$ after another
$c$ splits.

Applying this observation to the very start of the game, we initially have a
single pile of $\gamma n$ coins, then two piles of at most $\gamma n/2$ coins
each after the first split, then four piles of at most $\gamma n/4$ coins
after another two splits, and so forth. Generally, $n_{i}\leq\gamma
n/2^{\MT@delim@Auto\floor@star{\log_{2}i+1}}$.

From the above observation, $n_{2K}\leq\gamma n/K$, and from the proof of
Claim 4 we have $n_{i+K}\leq n_{i}/2$. The early termination of the game means
that $n_{i}\geq(\gamma-1)n/K$ for all $i$, thus

$\displaystyle i$ $\displaystyle\leq 2K+K\log_{2}\left(\frac{\gamma
n}{K}\cdot\frac{K}{(\gamma-1)n}\right)=K\cdot\left(2+\log_{2}\left(\frac{\gamma}{\gamma-1}\right)\right)\,.$

##  Appendix C Proofs from § 4

See 15

######  Proof C.1.

Let $\left|A_{i}\right|$ denote the number of elements that hash (according to
$h$) into a fixed bucket $A_{i}$, for some $i\in\left\\{1,\ldots,M\right\\}$.
Then $\mathbb{E}\\!\left[{\left|A_{i}\right|}\right]=n^{1-\alpha}$, since we
have $n$ elements hashing into $M=n^{\alpha}$ buckets. Recall that the
capacity of each bucket is $C=N/M$, where $N=n-n^{\beta}$, and so
$C=n^{1-\alpha}-n^{\beta-\alpha}$. We now apply a Chernoff bound for the lower
tail of $\left|A_{i}\right|$:

$\displaystyle\Pr\\!\left[{\left|A_{i}\right|<C}\right]=\Pr\\!\left[{\left|A_{i}\right|<\left(1-1/n^{1-\beta}\right)\cdot
n^{1-\alpha}}\right]\leq$ $\displaystyle\exp\left(-1/2\cdot n^{1-\alpha}\cdot
1/n^{2-2\beta}\right)$ $\displaystyle=$ $\displaystyle\exp\left(-1/2\cdot
n^{2\beta-\alpha-1}\right)\;.$

The claim follows by setting $\alpha$ and $\beta$ such that the above
probability is at most $1/n^{c+\alpha}$ and then doing a union bound over all
buckets.

See 4.2

######  Proof C.2.

We first optimize for the cost of $\textsf{SortUnif}_{1}(A,n)$ from Claim 16.
Note that the cost is (asymptotically) minimized when $n^{\beta}=\Theta(C)$,
that is, when $n^{\beta}=\Theta(n^{1-\alpha})$. We thus set $\beta=1-\alpha$.
We now verify the conditions from Claim 15 and set

$\alpha=\frac{1}{3}-\frac{\ln\ln n+\ln(2(c+1))}{3\ln n}\;.$

Then $n^{\frac{1-\alpha}{2}}=n^{\frac{1}{3}}\cdot n^{\frac{\ln\ln
n+\ln(2(c+1))}{6\ln n}}=n^{\frac{1}{3}}\cdot\exp\left(\frac{\ln\ln
n+\ln(2(c+1))}{6}\right)$ and the claim follows.

See 4.3

######  Proof C.3.

We prove the claim by induction on $k$. We assume that the statement is true
for $k$ and we then prove it for $k+1$. From the proof of Claim 15, we have
that the buckets in $\textsf{SortUnif}_{k+1}$ are not full with probability at
most $1/n^{c}$ as long as

$\beta\geq\frac{1}{2}\cdot\left(1+\alpha+\frac{\ln\ln n+\ln(2(c+1))}{\ln
n}\right)\,.$ (2)

We now would like to have the same upper bound for the probability that
$\textsf{SortUnif}_{k}$ fails in some bucket. For that, we invoke the
inductive hypothesis with failure probability at most $1/{n^{c+1}}$, and do a
union bound over the $n^{\alpha}$ buckets. We implicitly assume here that
$\alpha<1$, so that we have $2n^{\alpha}\leq n$. We upper bound $C$ by
$n^{1-\alpha}$ and get that the cost for all the buckets is

$O\left(n^{(1-\alpha)/f_{k}}\cdot\exp\left(1/4\cdot\ln\ln
n+B_{k}\cdot\ln(2(c+2))\right)\right)\;.$

The cost across the buckets and the backyard remains $O(1)$, and the cost of
the backyard is $O(n^{\beta/2})$ as before. We now equate

$\frac{1-\alpha}{f_{k}}+\frac{1/4\cdot\ln\ln n+B_{k}\ln(2(c+2))}{\ln
n}=\frac{\beta}{2}$

and then set

$\alpha=\frac{4-f_{k}}{4+f_{k}}+\frac{f_{k}}{f_{k}+4}\cdot\frac{4B_{k}\cdot\ln(2c+4)-\ln(2c+2)}{\ln
n}$

to satisfy Eq.(2). We would then get that

$\frac{1-\alpha}{f_{k}}=\frac{2}{4+f_{k}}-\frac{1}{4+f_{k}}\cdot\frac{4B_{k}\cdot\ln(2c+4)-\ln(2c+2)}{\ln
n}$

and the exponent in the overall cost would be

$\frac{2}{4+f_{k}}+\frac{1/4\cdot\ln\ln
n+B_{k}\cdot\ln(2c+4)-\frac{4B_{k}}{4+f_{k}}\cdot\ln(2c+4)+\frac{1}{4+f_{k}}\ln(2c+2)}{\ln
n}\;.$

Note that $2/(4+f_{k})=1/f_{k+1}$ by definition, so the only thing left to
verify is that:

$B_{k}\cdot\ln(2c+4)-\frac{4B_{k}}{4+f_{k}}\cdot\ln(2c+4)+\frac{1}{4+f_{k}}\ln(2c+2)\leq
B_{k+1}\cdot\ln(2c+2)\;.$

We upper bound $\ln(2c+4)\leq 2\ln(2c+2)$ and get that it is enough to show
that

$2B_{k}\cdot\left(1-\frac{4}{4+f_{k}}\right)+\frac{1}{4+f_{k}}\leq B_{k+1}\;.$

Finally, we use the fact that $1/8\leq 1/(4+f_{k})\leq 1/4$ to show that this
inequality holds when we set $B_{k}=k/4$.

See 1.5

######  Proof C.4.

To get an overall bound, we invoke Lemma 4.3 for $c=1$ and a value $k$ that
leads to a small cost. We set $x=1/2^{k-1}$ and rewrite $k=\log_{2}(2/x)$ in
the main term in the cost as follows:

$n^{1/f_{k}}\cdot 4^{k/4}=n^{1/(4-x)}\cdot\sqrt{2/x}=\exp(\ln
n/(4-x)+1/2\cdot\ln(2/x))=\exp(\ln(2)/2+f(x))\;,$

where we defined $f(x)=\ln n/(4-x)-1/2\cdot\ln(x)$. This function is minimized
at $x_{0}=4+\ln n-\sqrt{\ln^{2}n+8\ln n}$, so we invoke
$\textsf{SortUnif}_{k_{0}}(A,n)$ for $k_{0}=\log_{2}(2/x_{0})$, yielding:

$\displaystyle f(x_{0})$ $\displaystyle=\frac{\ln n}{\sqrt{\ln^{2}n+8\ln
n}-\ln n}-\frac{1}{2}\cdot\ln(4+\ln n-\sqrt{\ln^{2}n+8\ln n})\leq\frac{\ln
n}{4}+\frac{1}{2}\;.$

Plugging $f(x_{0})$ and $k_{0}$ back, we get an overall cost of $O((n\ln
n)^{1/4})$. As the optimal (offline) cost is clearly $\Omega(1)$ with high
probability, the claim follows.

###  C.1 Proofs from § 4.1

In this subsection we prove the following claim characterizing the cost of the
algorithm presented in § 4.1. See 17

A central concept for our analysis is that of the _run_. A run denotes a
maximal contiguous subarray of filled cells $A[i]$ through $A[j]$ such that an
element $x\in\left[\frac{i}{\beta n},\,\frac{j+2}{\beta n}\right)$ will be
placed in cell $A[j+1]$. Generally, long runs are to be avoided as they make
it more likely that an element $x$ is placed far away from $A[h(x)]$, which
makes it more difficult to bound the cost incurred by neighboring elements.

The issue of wraparound. When analyzing linear probing one can often disregard
the issue of wraparound as a technical corner case which has no impact on the
procedure at hand other than to complicate notation and definitions. For our
use case however, wraparound would mean that we place a large value at the
start of the array – a region that we, intuitively, have otherwise been
filling with small values.

Wraparound could thus incur quite a penalty, and we will prove that, w.h.p.,
no wraparound will happen. In this way, wraparounds can be disregarded in the
following arguments. Formally, let $\mathcal{W}$ denote the event that
$\mathcal{A}$ experiences wraparound during execution, so that some element
$x$ is placed in a cell of index smaller than $h(x)$. We then compute the
expected cost of $\mathcal{A}(X)$ as
$\mathbb{E}\\!\left[{\mathcal{A}(X)}\right]=\mathbb{E}\\!\left[{\mathcal{A}(X)\cdot\left[{\mathcal{W}}\right]}\right]+\mathbb{E}\\!\left[{\mathcal{A}(X)\cdot\left[{\neg\mathcal{W}}\right]}\right]$.

######  Claim 18.

$\mathbb{E}\\!\left[{\mathcal{A}(X)\cdot\left[{\mathcal{W}}\right]}\right]\leq
O\left(\frac{1}{n}\right)\,.$

######  Proof C.5.

First, note that the cost of _any_ solution will be at most $n$. Hence the
claim follows when we have shown that $\Pr\\!\left[{\mathcal{W}}\right]\leq
O\left(\frac{1}{n^{2}}\right)$.

As each run starts in one of the first $\beta n$ cells, some run needs to be
of length at least $\alpha n$ to cover the buffer at the end of $A$, which is
a necessary condition for wraparound. For such a long run to occur, there must
in turn exist an interval $I\subset[0,\beta n]$ of length $\alpha n$ such that
there are at least $\alpha n$ values $x\in X$ with $h(x)\in I$. Denote the
number of such elements by $X_{I}$.

As $X_{I}$ is the sum of independent trials, each with success probability
$\alpha/\beta$, we can bound the probability of $X_{I}$ exceeding $\alpha n$
by a Chernoff bound. Setting $\delta=\beta-1$ and
$\mu=\mathbb{E}\\!\left[{X_{I}}\right]=n\cdot\alpha/\beta$ we have, for any
fixed $\alpha,\beta$,

$\Pr\\!\left[{X_{I}>\alpha
n}\right]=\Pr\\!\left[{X_{I}>(1+\delta)\mu}\right]\leq\exp\left(\frac{-\delta^{2}\mu}{2+\delta}\right)=\exp\left(\frac{-(\beta-1)^{2}\frac{\alpha}{\beta}n}{1+\beta}\right)\leq
O\left(\frac{1}{n^{4}}\right)\,.$

By a union bound over all $\beta n$ intervals we get
$\Pr\\!\left[{\mathcal{W}}\right]\leq O(\beta/n^{3})\leq O(1/n^{2})$.

Bounding the cost of the solution. We account for three types of cost in
$\mathcal{A}(X)$: If the $i$-th element is inserted in a cell right before the
start of a run, the $i$-th step is said to incur a _merge_ cost, denoted
$mer(i)$, as it potentially merges two runs. If the $i$-th element is inserted
in the cell following a run, the $i$-th step is said to incur an _extend_
cost, denoted $ext(i)$, as it extends the run. If the $i$-th insertion does
not give rise to a merge- (resp. extend-) cost, we set $mer(i)=0$ (resp.
$ext(i)=0$). Finally we have to account for the cost between values $A[i]$ and
$A[j]$ separated by one or more empty cells. This cost is not charged to a
specific insertion performed by the algorithm but is instead viewed as a
property of the solution, $sep(\mathcal{A}(X))$.

We bound the expected size of each type of cost in the following three claims,
and together they account for the value of the solution produced by
$\mathcal{A}$.

######  Claim 19.

$\displaystyle\sum_{i=1}^{n}\mathbb{E}\\!\left[{mer(i)\cdot\left[{\neg\mathcal{W}}\right]}\right]\leq\frac{1}{\beta
n}\sum_{i=1}^{n}\mathbb{E}\\!\left[{s(i)}\right]+\frac{1}{\beta}\,.$

######  Proof C.6.

Let $x_{i}$ be the $i$-th element of $X$ and let $k$ be the index where
$x_{i}$ is placed. Then $s(i)=1+k-h(x_{i})$, due to our assumption that no
wraparound occurs. Let $y=A[k+1]$ be the value in the neighbouring cell, which
was inserted before $x_{i}$. Then $mer(i)=\left|y-x_{i}\right|$.

As cell $A[k]$ was empty at the time of $y$’s insertion we must have
$y\in\left[\frac{k+1}{\beta n},\,\frac{k+2}{\beta n}\right)$. Meanwhile,
$x_{i}\in\left[\frac{h(x_{i})}{\beta n},\,\frac{h(x_{i})+1}{\beta n}\right)$
and thus

$\left|y-x_{i}\right|\leq\frac{k+2-h(x_{i})}{\beta n}=\frac{s(i)+1}{\beta
n}\,.$

It follows that
$\sum_{i=1}^{n}\mathbb{E}\\!\left[{mer(i)\cdot\left[{\neg\mathcal{W}}\right]}\right]\leq\frac{1}{\beta
n}\sum_{i=1}^{n}\mathbb{E}\\!\left[{s(i)}\right]+\frac{1}{\beta}$.

######  Claim 20.

$\sum_{i=1}^{n}\mathbb{E}\\!\left[{ext(i)\cdot\left[{\neg\mathcal{W}}\right]}\right]\leq\frac{1}{\beta
n}\sum_{i=1}^{n}\mathbb{E}\\!\left[{s(i)}\right]\,.$

######  Proof C.7.

Denote by $I_{k}$ the $k$-th run in $A$ which spans cells $A[a_{k}]$ through
$A[b_{k}]$ before the insertion of $x_{i}$, with value $y_{k}=A[b_{k}]$ in the
final position. Assuming no wraparound occurs, we have $a_{k}\leq b_{k}$. In a
slight abuse of notation we denote by $h(x_{i})\in I_{k}$ the event that
$x_{i}$ is appended to $I_{k}$, which is equivalent to the event
$h(x_{i})\in[a_{k},b_{k}+1]$. Assuming $h(x_{i})\in I_{k}$, we then have
$s(i)=1+(b_{k}+1)-h(x_{i})=2+b_{k}-h(x_{i})$. Then

$\displaystyle
ext(i)=\sum_{k=1}\left|x_{i}-y_{k}\right|\cdot\left[{h(x_{i})\in
I_{k}}\right]\leq\sum_{k=1}\frac{1}{\beta
n}\left(\left|h(x_{i})-h(y_{k})\right|+1\right)\cdot\left[{h(x_{i})\in
I_{k}}\right]\,.$

As we are interested in $\mathbb{E}\\!\left[{ext(i)}\right]$ we wish to bound
$\mathbb{E}\\!\left[{\left|h(x_{i})-h(y_{k})\right|\cdot\left[{h(x_{i})\in
I_{k}}\right]}\right]$ for some fixed $k$. We will not delve into the
distribution of $h(y_{k})$ but note that the distribution of $h(x_{i})$ is
independent of $h(y_{k})$. Conditioning on $h(y_{k})$, we see that the
expectation is maximized when $h(y_{k})$ is at one of the “extremes”
$h(y_{k})=a_{k}$ or $h(y_{k})=b_{k}$. For ease of computation we substitute
$h(y_{k})=b_{k}+1$ for our upper bound:

$\displaystyle\mathbb{E}\\!\left[{\left|h(x_{i})-h(y_{k})\right|\cdot\left[{h(x_{i})\in
I_{k}}\right]\cdot\left[{\neg\mathcal{W}}\right]}\right]$
$\displaystyle\leq\mathbb{E}\\!\left[{\left|(b_{k}+1)-h(x_{i})\right|\cdot\left[{h(x_{i})\in
I_{k}}\right]}\right]$
$\displaystyle=\mathbb{E}\\!\left[{(s(i)-1)\cdot\left[{h(x_{i})\in
I_{k}}\right]}\right]\,.$

Plugging into our previous equation we obtain

$\displaystyle\mathbb{E}\\!\left[{ext(i)\cdot\left[{\neg\mathcal{W}}\right]}\right]$
$\displaystyle\leq\frac{1}{\beta
n}\sum_{k=1}\mathbb{E}\\!\left[{s(i)\cdot\left[{h(x_{i})\in
I_{k}}\right]}\right]\leq\frac{1}{\beta
n}\cdot\mathbb{E}\\!\left[{s(i)}\right]\,.$

######  Claim 21.

$\mathbb{E}\\!\left[{sep(\mathcal{A}(X))\cdot\left[{\neg\mathcal{W}}\right]}\right]\leq
2\,.$

######  Proof C.8.

Let the runs be numbered $1,\dots,r$ according to their order in $A$, and say
that the $i$-th run covers cells $A[a_{i}]$ through $A[b_{i}]$ such that
$a_{i}\leq b_{i}<a_{i+1}\leq b_{i+1}$. With this notation
$sep(\mathcal{A}(X))=\sum_{i=1}^{r}\left|A[a_{i+1}]-A[b_{i}]\right|$.

Fix some $i$, let $x=A[a_{i+1}]$ and $y=A[b_{i}]$. First, observe that
$h(x)=a_{i+1}$. Had $h(x)$ been lower, $x$ would have been placed in a cell of
smaller index (and we know that $A[a_{i+1}-1]$ is empty). Had $h(x)$ been
higher, $x$ would have been placed in a cell of index at least $a_{i+1}$ due
to our assumption that no wraparound occurs. Hence
$A[a_{i+1}]\in\left[\frac{a_{i+1}}{\beta n},\,\frac{a_{i+1}+1}{\beta
n}\right)$.

Similarly, we have $a_{i}\leq h(y)\leq b_{i}$ and thus
$A[b_{i}]\in\left[\frac{a_{i}}{\beta n},\,\frac{b_{i}+1}{\beta n}\right)$, as
the element $y$ would otherwise have been placed outside of the run. Thus

$\displaystyle\sum_{i=1}^{r}\left|A[a_{i+1}]-A[b_{i}]\right|\leq\sum_{i=1}^{r}\frac{a_{i+1}-a_{i}+1}{\beta
n}=\frac{a_{r}-a_{1}+r}{\beta n}\leq 2\,$

as $r\leq a_{r}\leq\beta n$.

Summing over Claims 18, 20, 19 and 21, we obtain the bound stated in Claim
17.∎