Randomness in built-in .sort

[Stewart Gordon]

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.