search

Morwenn / cpp-sort

Sorting algorithms & related tools for C++14
MIT License
624 stars 58 forks source link

Any interest for a splay sort implementation? #201

Closed carlopi closed 2 years ago

carlopi commented 2 years ago

I could contribute with a somehow decent splay-sort implementation. Basically it works by insert elements one by one in a splay tree + visit of the tree ordering the data.

Main advantage, as with tim-sort, is that's it's adaptive (& stable). Main drawback is that it requires 2 pointers per element memory overhead.

Not sure whether this could make sense with the approach / scope of this library.

Morwenn commented 2 years ago

A splaysort certainly falls in the scope of the library, especially since I like interesting adaptive comparison sorts. An implementation would be welcome as long as all tests pass - which I can help with.

Ideally I want to make a separate library for extras and contributions (see #147), but I haven't started the work on it and I'm not working much lately, so you can ignore it and make a PR to the main repository (here) instead.

carlopi commented 2 years ago

Perfect, I will have to review the implementation and adapt it, I will ping when I am closer to something ready to be merged.