You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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 text was updated successfully, but these errors were encountered:
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 text was updated successfully, but these errors were encountered: