Bill Baxter wrote:
<snip>
I think the built-in sort should be some kind of stable sort. Also
the stability or lack thereof is not mentioned in the spec, and it
probably should be because stability is critical for some uses of
sorting. One shouldn't have to guess whether a given implementation
of D will use a stable sort or not.
--bb
A stable sort can be slower than an unstable sort. There are many cases
where the order of equally-ranking keys does not matter or it has no
effect whatsoever (e.g. sorting an array of integers). Then why take
the extra overhead of making the sort stable?
We could have an extra property .stableSort, for those cases where you
need stability. Of course, it would be valid to implement .sort and
.stableSort with the same algorithm, though to do so would be naive
unless someone comes up with a stable sorting algorithm with O(n log n)
or better time complexity and O(log n) or better extra memory
requirement. But in the absence of such an algorithm, the compiler
could still replace .stableSort with .sort in those cases where it can
guarantee it will make no difference to the end result.
Or you could argue that requiring sort to be stable is sufficiently
uncommon that it might as well be left to a library function.
Stewart.
