DeltaSort: Incremental sorting of arrays with known updates

When records need to be read in a particular order, sorting at query time incurs repeated $\Theta(n \log n)$ cost for an array of $n$ records and can become a bottleneck in read-heavy workloads. A common solution is to maintain a derived sorted read-replica that is kept updated as the underlying system-of-record changes. For updating read-replicas that are stored as arrays, existing approaches rely on either full re-sorting or incremental algorithms such as binary insertion or merge-based sort. In this paper, we study incremental sorting under a new model in which the sorting routine is explicitly informed of the $k$ indices updated since the previous sort—a setting that naturally arises in systems that track updates. Under this model, we present DeltaSort, a new algorithm that runs in $O(n\sqrt{k})$ expected time using $O(k)$ auxiliary space under a random update model, and outperforms existing algorithms for small update batches in our experimental evaluation.