An update-aware approach to incremental sorting (DeltaSort)
Paper (PDF): https://github.com/shudv/deltasort/blob/main/paper/main.pdf 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…
What it does
In the maker’s words, at launch
Paper (PDF): https://github.com/shudv/deltasort/blob/main/paper/main.pdf 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!
Does the same job
all alternatives →- SPSortraits, Portraits of Sorting Algorithms2019 · wtracy.gitlab.io · ▲132
- IQIllustrated Quicksort algorithm2017 · illustrated-algorithms.now.sh · ▲187
- RERetool: Excel-like, with higher order primitives2017 · retool.in · ▲190
- HIHeap is a new approach to analytics. Just capture everything2013 · heapanalytics.com · ▲339
More dev tools this month
the category →
Open-source GTM skills for technical founders
Dev tools · 29d ago · gtmcofounder.com
OpenTrailPaper is open-source bike computer firmware for the LilyGO T5S3 4.7" E-Paper PRO. It supports offline maps, GPX routes, FIT recording and Bluetooth sensors.
Dev tools · 1d ago · opentrailpaper.com
Launched alongside, January 2026
the whole month →- IN
Hey HN! I wanted to share something I built over the last few weeks: isometric.nyc is a massive isometric pixel art map of NYC, built with nano banana and coding agents. I didn't write a single line of code. Of course no-code doesn't mean no-engineering. This project took a lot more manual labor than I'd hoped! I wrote a deep dive on the workflow and some thoughts about the future of AI coding and creativity: http://cannoneyed.com/projects/isometric-nyc
AI · Jan 2026 · cannoneyed.com
Automatic AI-powered code reviews the moment you open a PR
Dev tools · Jan 2026 · kilo.ai
