  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.
