Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve the state of mergesorts #175

Open
Morwenn opened this issue Nov 12, 2020 · 0 comments
Open

Improve the state of mergesorts #175

Morwenn opened this issue Nov 12, 2020 · 0 comments

Comments

@Morwenn
Copy link
Owner

Morwenn commented Nov 12, 2020

The library contains a bunch of mergesort variants, and at least three of them will adapt depending on how much memory is provided. However they follow different strategies:

  • grail_sort is a buffered sorter, but its default instantiation is one that doesn't use a buffer.
  • wiki_sort is similar but uses by default a static buffer of 512 elements.
  • merge_sort doesn't let a choice to users, std::stable_sort style, and handles it own allocations, with an allocation scheme allowing it to allocate more than once if needed.

I don't know what should be done, but bringing some uniformity to the table could be good. Also, more urgent: the stable sort benchmarks need to be redone since they are currently unfair by virtue of benchmarking several mergesort variants with varying amounts of heap memory available. There should be at least two different benchmarks: one with O(n) memory available and one with O(1). Being thorough with regard to all the allocations in-between is more complicated and can be considered later.

Having a versatile interface for memory buffers would be nice. Currently there's also no allocator support, which might be something desirable.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant