Optimizing Java using D

[Andrea Fontana 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]
> [...]

I'm sorry if i'm going to say some stupid things, but I'm still 
not sure about this.

You said: "you can prove that there exists some unstable sort 
that is always faster than a stable sort"

First of all: stable sort are also unstable, ok, but I think you 
meant: "you can prove that there exists some unstable sort - that 
it isn't a stable sort too -  that is always faster than a stable 
sort", didn't you?

With your example you're showing that is this specific case is 
faster, you're not proving that is *always* faster (btw, i think 
you meant equal or faster).

In my opinion you're just proving that for *swap-based 
algorithms* number of swaps you need to unstable sorting is 
always *less or equals* to the number of swaps you need to stable 
sorting.

Anyway some sorting algorithms don't use comparison between 
elements so swap doesn't make any sense. Radix sort, for example, 
never compares two elements. It "directly" write the output 
array, so I don't think the number of swaps is the right metric. 
Counting sort doesn't do any comparison too, and it doesn't swap 
elements.

Moreover you're assuming it should work "in-place". Usually we 
need a sorted copy, so you can't just swap that elements, you 
need to copy the other elements too and then apply your swaps 
over copy. If element are complex you have to copy element to new 
array one-by-one.

Using your example a 
"magical-stable-sort-without-swaps-planning-algorithm" could 
guess that we just need to prepend last element before the first 
one: it is a stable sort. There's no swap at all. And we copy 
exactly n elements. (and it's faster than copy all n elements and 
then do the swap).