DeltaSort: Incremental repair for sorted arrays for known updates

This paper studies the problem of maintaining sorted order under incremental updates when the indices of modified elements are explicitly known. While most production sorting routines operate under a blind model and must rediscover structure from scratch, many real systems track which elements have changed but do not exploit this information during sorting. Under this update-aware model, the paper presents DeltaSort, an incremental repair algorithm for sorted arrays that batches multiple updates and coordinates their repair. The algorithm leverages a pre-sorting phase that induces directional segmentation of updates, followed by stack-based processing to avoid redundant comparison work and overlapping data movement. The paper provides a formal problem definition, a detailed description of the algorithm, a correctness proof, and an empirical evaluation across a range of array sizes and update volumes. The results demonstrate that DeltaSort achieves substantial practical speedups over blind native sorting and repeated binary insertion for sparse and moderately dense updates, with a clear crossover point beyond which full re-sorting becomes preferable. This work is intended as a step toward tighter integration between update pipelines and sorting routines in read-heavy systems and algorithm engineering contexts.