Morwenn / vergesort

Unstable O(n log n) sorting algorithm with O(n) memory
MIT License
60 stars 6 forks source link

Consider using gfx::timmerge instead of std::inplace_merge #14

Open vedgy opened 3 years ago

vedgy commented 3 years ago

I see that vergesort uses std::inplace_merge a lot. Could it be sped up by using the recently exposed gfx::timmerge instead, at least in some places? According to my benchmarks, when gfx::timmerge is slower than std::inplace_merge, it is usually only slightly so. When faster, however, it often wins big. The merge algorithm could become a template argument to avoid a hard dependency on the timsort library and facilitate experimenting with other merge algorithms.

Morwenn commented 3 years ago

This project is mostly a proof-of-concept one than a production-ready one tbh, and as things are today I could rather decrease the amount of code in than increase it - I'm never quite sure what to do with this repository and how much I should strip it to the bare minimum.

There's indeed a bunch of improvements that could be done in the merging area (see #4 and #5 for example), but since it's already a win when merging happens, I considered that it was good enough for a proof-of-concept. I don't really consider vergesort to be a great solution to real-world problems anyway, and it's not super interesting from a comp-sci point of view either. As far as generalization goes, I could give options to change the underlying sorting algorithm, to make the vergesort layer stable, to change the underlying merge algorithm, or to change the function used to determine what a "big enough" run is, but at the end of the day I don't think it will really make the algorithm more interesting or useful :/