At this moment we have 2 sorting methods for slices:
sortwhich is stable but allocates memory for merge sort. It is slow.
sort_unstablewhich uses log N memory but always on stack so not dynamic allocations.
I think, there is possible that someone would need both stable sorting and lack of allocations. After some thought, I come up with such solution:
- Add new method
sort_stable_with_mem(&mut self, &mut [MaybeUninit<Self::Item>])which accepts buffer with same size as self, and uses it for sorting.
sort()may be a wrapper around new method which checks if slice sorted, then allocates buffer and calls new method.
So, users would be able to provide place on the stack or reuse temporary allocation for multiple sorts.
- Use some stable non-allocating sort algorithm. I think, they are slower even if don't allocate. Which even worse if we use some smart allocator like jeMalloc or MiMalloc.
- Accept allocator as generic parameter (same as
Boxdoes). I think, this is more complex way and would some use-cases more difficult (e.g. instead of just reusing allocations, there is need to write
unsafecode for allocator). Users which have Allocator written can just use it to allocate memory using it before
sort_stable_with_memcall very easily.
Maybe there are another options.
What do you think? Also, maybe this is not very useful to be added to standard library and users can just use some crate for this.