Sometimes we need to deal with huge arrays, in which case we risk overflowing the stack by using Quicksort-based techniques whose space complexity is O(ln(n)) due to its recursive call stack. It is possible yet tricky to perform sorting with constant space and decent performance, i.e. O(n*ln(n)*ln(n)) or better, so I think the standard library could provide a sort_const_space method on slice.
What are your thoughts? Would you prefer an extra method in the standard library or a separate crate? Which exact algorithm do you propose for this task?
Given a quick look at the code, the current implementation of slice::sort is not recursive (it's a merge sort that allocates (len / 2) space on the heap), so it does not create the issue of stack overflow.
I imagine there are platforms with very limited memory where hyper-optimizing for memory usage could be beneficial. It's sufficiently niche that it's not clear it should be part of the standard library. Building it as an external crate (and profiling it, and finding what cases need it in practice) would be a logical way forward.
Note that the current slice::sort_unstable_* methods, which use quicksort, limit the recursion to floor(log2(slice.len()))+1 levels, after that they use heapsort.
Can you say more about the scenario in which logarithmic space usage is a problem? I've never seen a well-implemented quicksort have such a problem -- either it's introsort and switches to heapsort after a while, or it does some form of smart pivoting to keep from ever hitting worse-than-logarithmic behaviour.
