Optimizing Java using D

[Andrei Alexandrescu via Digitalmars-d]

On 6/23/14, 9:33 AM, Chris Cain wrote:
> Or, to look at it another way, all "stable" sorts satisfy the qualities
> needed by an "unstable" sort, but not all "unstable" sorts satisfy the
> qualities of a "stable" sort. The minimum number of swaps/operations to
> create a sorted array won't necessarily maintain the stability property
> of the elements.

Yeah, it's really simple: the set of unstable sorting algorithms 
includes the set of stable sorting algorithms, so unstable sorting is 
vacuously "at least as good or better".

I'm baffled by the recurrent assertion that stable sort algorithms are 
somehow faster than unstable sort algorithms.

First, comparing entire sets of algorithms on unspecified input 
statistics is tenuous. A comparison would be between specific algorithms 
on specific data statistics.

Second, there are known reasons and setups where Timsort and derivatives 
fare better than classic quicksort-based implementations, and 
generalizing them into some magic "stable sort is just better" umbrella 
argument is just odd. Timsort works well on data with large continuous 
sorted runs, and that's an important case but one that a quicksort-based 
approach could and should avail itself of as well.

Third, again, anything stable is also unstable :o).


Andrei