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.
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_sortis a buffered sorter, but its default instantiation is one that doesn't use a buffer.wiki_sortis similar but uses by default a static buffer of 512 elements.merge_sortdoesn't let a choice to users,std::stable_sortstyle, 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.