We empirically study sorting in the evolving data model. In this model, a sorting algorithm
maintains an approximation to the sorted order of a list of data items while simultaneously,
with each comparison made by the algorithm, an adversary randomly swaps the order of
adjacent items in the true sorted order. Previous work studies only two versions of quicksort,
and has a gap between the lower bound of Ω (n) and the best upper bound of O (n log log
n). The experiments we perform in this paper provide empirical evidence that some …

We empirically study sorting in the evolving data model. In this model, a sorting algorithm
maintains an approximation to the sorted order of a list of data items while simultaneously,
with each comparison made by the algorithm, an adversary randomly swaps the order of
adjacent items in the true sorted order. Previous work studies only two versions of quicksort,
and has a gap between the lower bound of Omega (n) and the best upper bound of O (n log
log n). The experiments we perform in this paper provide empirical evidence that some …