Optimizing Java using D

[Chris Cain via Digitalmars-d]

On Monday, 23 June 2014 at 15:57:12 UTC, Andrea Fontana wrote:
> How can this be proven?
> Is it valid only for "swap-based" sorting algorithms?
>
> For example, radix sort is stable and its complexity is O(kn). 
> Is there a faster unstable sort?

It's not really about the time complexity but the absolute time 
it must take. But I showed the example that shows that the fact 
that any stable sort must do extra work:

[2,2,2,2,1]

An unstable sort may swap the first 2 and the 1 whereas a stable 
sort must, by definition, maintain the relative positioning of 
the 2s, which means it must move all of the 2s upwards. Think of 
a "magical" sort that knows exactly the perfect swaps to do in 
order to sort (that is, "magical" sort's complexity is O(n)). In 
the case above, "magical unstable sort" does 1 swap and "magical 
stable sort" must do 4 (if it doesn't, it's not stable). This 
shows that stable sorts must strictly be equal to or slower than 
unstable sort (and an unstable sort could sometimes do better 
than a stable sort).

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.