Optimizing Java using D

[Chris Cain via Digitalmars-d]

On Monday, 23 June 2014 at 15:19:15 UTC, Steven Schveighoffer 
wrote:
> Is it just me, or does this seem unintuitive? I would think a 
> stable sort requires extra care, i.e. extra time, to ensure 
> stability.
>
> Do we need an unstable sort then? Or is this a corner case? I 
> am fully ignorant on these advanced sorting routines and how 
> they work. The Quicksort-based sort routines are like black 
> magic to me, my knowledge stops at merge sort :)
>
> -Steve

Technically, you can prove that there exists some unstable sort 
that is always faster than a stable sort. Andrei showed me this 
once:

[2,2,2,2,1]

With unstable sort, the 1 and first 2 could be swapped, but with 
stable sort, the 1 must swap with each 2 until it settles into 
the 0th position.

That said, I've never seen the unstable sort that's always faster 
than any stable sort and since it doesn't appear in any of the 
languages I know of, I've got to guess that no one else has 
discovered it either.

That said, I've seen some cases where the unstable sort is faster 
(particularly in cases where the ordering of the elements is 
nearly completely random), so it's not as if unstable sort is 
currently always worse. It's just in many real-world scenarios it 
ends up being worse. Furthermore, our stable sort (an 
implementation of Timsort) is impossible to really use 
"incorrectly" ... even using it very "stupidly" (as an example, 
append an element on the end of a sorted array and "insert" it by 
calling stable sort) will result in reasonable runtimes and do 
what the programmer expects of it. It makes writing simple quick 
scripts and prototypes absurdly easy and still very efficient. 
Plus maintaining the current order of the elements is really nice 
in general.

Personally, I'm still in the camp of suggesting that our default 
should be stable sort and if you're certain your use case will 
benefit from the extra speed of unstable sort, you should specify 
it. But I don't think that's going to change.