[deathanatos]

The author covers this pretty much exactly as you describe it. From Part 2 of TFA,

> Let’s look at the sort step, which is the bottleneck of the algorithm according to the analysis.

> You can see that most of the time, the sort does nothing at all! The list is almost always already sorted from the previous frame.

> Even when it becomes unsorted, it usually just takes a couple of swaps to be sorted again.

> Here’s insertion sort in action:

[tialaramex]

If you use a modern sort, it'll just go "Oh that's sorted, we're done". Pattern Defeating Quicksort will do that and so would Glidesort, Driftsort, IPNsort and so on. Most of these algorithms will also correctly shortcut trivial "almost sorted" cases like 123457689 (only longer, if you really only have nine elements you want a custom sort for that, there will be a correct algorithm and it's probably written down somewhere already)

Rust's old sorts, both of them, get this right. There's a fair chance the current version of your C++ stdlib even gets this right in its unstable sort. In 1965 it's understandable that you reach for an insertion sort for this case, in 2024 it's embarrassing if your language doesn't provide a built-in sort where this just works.

[nextaccountic]

> Rust's old sorts, both of them, get this right.

And the newer sort in the stdlib does too, right?

Link https://www.reddit.com/r/rust/comments/1dl079x/the_rust_stdl...

[tialaramex]

Yes, the stdlib provided sort and sort_unstable in Rust 1.81 and later are

https://github.com/Voultapher/sort-research-rs/blob/main/wri... and https://github.com/Voultapher/sort-research-rs/blob/main/wri...

[maccard]

You don’t just want to sort the data, you actually want to collect a list of overlapping pairs, (or more like you want to collect the list of pairs that have changed since last time).

Using a built in sort will give you the same complexity, but iterating over 10000 elements again to gather this list is an overhead that you can avoid with a DIY approach

[eru]

For what it's worth, Haskell's built-in sort does this, and I think Python, too. (But I'm not as confident about Python. My memory is a bit hazy.)