I’ve been exploring a variant of the sorting problem where the sort routine knows about which indices were updated since the previous sort.
This situation arises in many practical systems: large sorted lists that are read frequently, updated in small batches, and where the update pipeline already knows which positions changed (e.g., UI lists, leaderboards). Despite this most systems either re-sort the entire array or apply independent binary insertions or perform extract-sort-merge.
In the paper, I propose DeltaSort, an incremental repair algorithm for this update-aware model - which is able efficiently batch together multiple updates and avoid a full re-sort. Initial experiments with a Rust implementation show multi-fold speedups over repeated binary insertion and native sorting (sort_by) for update batch size up to 30%.
I’m mainly looking for technical feedback from people who’ve worked on sorting, data structures, or systems: 1. Am I missing prior work that already addresses this model or technique? 2. Are the baselines and comparisons reasonable? Is there a better (stricter) baseline that we can use to compare DeltaSort? 3. How useful does this seem in real systems, outside of the benchmarks I have used?
Thanks - and happy to discuss details!
