Since you have Timsort in there, would you maybe also be interested in peeksort and powersort?

[JobLeonard]

Given how interested you clearly are in sorting algorithms I would not be surprised if you are probably aware of these algorithms, but a quick search didn't show anything in the repo so that's why I'm mentioning it them

https://www.wild-inter.net/publications/munro-wild-2018

The TL;DR is that there is a bug in Timsort's merging rules, and provably fixing them lead to two new algorithms: peeksort and powersort. Powersort has recently been picked to replace Timsort in Python.

Here is Sebastian Wild, one of the authors of the paper introducing the algorithms, giving a presentation about it at PyCon US 2023:

https://www.youtube.com/watch?v=XjOnY-OLAPc

There is also multi-way powersort: https://www.wild-inter.net/publications/cawley-gelling-nebel-smith-wild-2023.pdf

Anyway, just bringing it to your attention.

[Morwenn]

Hi, I actually a branch with powersort at some point, I'm not sure why I never merged it but I think it was a scalability issues with some sizes of difference_type.

At some point I toyed with the idea of providing a tool in the library to easily generate timsort-like sorts by allowing users to decide how they resolve the runs merging order of the overall algorithm, but I never got a satisfying API either, so it kind of fell flat. The more recent addition of adaptive Shivers sort lately was only because the required changes to the existing code were very minor - and even then I think I encountered a bug with it at some point, but I never documented it in an issue so I also forgot what it was all about 😅

[JobLeonard]

I can imagine things can get pretty complex when it comes to keeping all of these different sorting algos happy while also having the flexibility regarding all of the options this library provides.

Thanks for the update!

[Morwenn]

Yeah, I've got to admit that time became an issue lately and that I don't have as much time to integrate new algorithms and keeping them to a high level of quality, so I occasionally add new ones but not as often as I could. I wouldn't be surprised if the library stayed rather calm on that front for at least six months.

I am trying to generally improve the quality of the library and tooling itself instead, to become a useful tool for people who want to develop and test sorting algorithms. Having a collection of ready-to-use algorithms is nice, but at the end of the day the main value of the library is helping people who write sorting algorithms in C++, so I want to try and focus on that a bit. If I ever find time and motivation again - which will eventually happen, I just don't know when -, I will probably start integrating new algorithms again. And if I'm lucky there will already be quality implementations around that I can just pickup and adapt a bit haha