  We study comparison sorting in the evolving data model [AKMU11], where the
true total order changes while the sorting algorithm is processing the input.
More precisely, each comparison operation of the algorithm is followed by a
sequence of evolution steps, where an evolution step perturbs the rank of a
random item by a "small" random value. The goal is to maintain an ordering that
remains close to the true order over time. Previous works have analyzed
adaptations of classic sorting algorithms, assuming that an evolution step
changes the rank of an item by just one, and that a fixed constant number $b$
of evolution steps take place between two comparisons. In fact, the only
previous result achieving optimal $O(n)$ total deviation from the true order,
where $n$ is the number of items, applies just for $b=1$ [BDEGJ18].
  We analyze a very simple sorting algorithm suggested in [M14], which samples
a random pair of adjacent items in each step and swaps them if they are out of
order. We show that the algorithm achieves and maintains, w.h.p., optimal total
deviation, $O(n)$, and optimal maximum deviation, $O(\log n)$, under very
general model settings. Namely, the perturbation introduced by each evolution
step follows a distribution of bounded moment generating function, and over a
linear number of steps, on average the number of evolution steps between two
sorting steps is bounded by an arbitrary constant.
  Our proof consists of a novel potential function argument that inserts "gaps"
in the list of items, and a general framework which separates the analysis of
sorting from that of the evolution steps, and is applicable to a variety of
settings for which previous approaches do not apply. Our results settle
conjectures by [AKMU11] and [M14], and provide theoretical support for the
empirical evidence that simple quadratic algorithms are optimal and robust for
sorting evolving data [BDEGJ18].
