This pitch relates to SR-306, which as of yesterday was tagged as Starter Proposal by Ben Cohen.
This pitch consists of three parts:
Some use cases require a stable sort. We should add a good implementation to the Standard Library, because:
- The commonly known Stable Sorts aren’t good on space complexity (eg classic MergeSort), and amongst the fast (linearithmic, or O(n log n)) ones, the best option is not obvious.
- The potential users of Stable Sorts aren’t experts on Sorting, and shouldn’t have to be, but the hardness of the topic requires expertise to implement and verify it.
Proposed Steps for a Solution
This is how I think we could proceed:
- Discuss if this is necessary.
- Discuss what the best possible algorithm for this could be.
- Lemme implement it.
- I formalize the proposal and send it for review.
Proposed Steps for an Implementation
If I implement it, I should do something like this:
- Implement MergeSort as a placeholder.
- Write tests for it: if the tests are correct for MS, they will be for whatever we pick as the final algorithm.
- Implement and test StableSort in place of MergeSort.
That’s more or less it. Here are the topics I haven’t covered:
- Naming (todo; bikeshed)
- API (I guess it should mimic or extend the current one used for Sorting)
- Optional admissible complexities, like quasilinear complexity (O(n log ^k n) with constant k)
Now onto the discussion.
Should we do In-Place MergeSort? Wikipedia says it’s O(n log^2 n). But I dunno how much it’s used. If it’s a rare sort, we shouldn’t use it.
I’d prefer to put into the StdLib an algorithm that is well known in its behavior and costs, since it would be used in many real-world applications.
That’s it. Thank you for reading!