Optimizing Java using D

[Wanderer via Digitalmars-d]

On Monday, 23 June 2014 at 16:33:13 UTC, Chris Cain wrote:
> 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.

Nobody, never, measures sort algorithms by amount of swaps.

Swapping two references is zero-cost operation; *comparing* two 
elements of an array is what's important. Because it requires 
comparison function calls, fields resolve/read, actual comparison 
math etc. That's why sort algorithms are always measured by 
amount of compares.

And both versions of sort - stable and unstable - for this 
particular example you demonstrated above - [2,2,2,2,1] - should 
involve all five elements in comparison. If your unstable sort 
only compares first and last elements, swaps them and returns, 
it's broken.