Quicksort vs. Shell

[Albert Chan]

(06-20-2014 02:12 PM)Claudio L. Wrote:  EDIT: Sort was made stable for all methods using method described in a post above.

What is the cost of making unstable sort stable?

I assume comparisons now cost doubled.

(L[i] < L[j])      → (L[i] < L[j] or (L[i]==L[j] and i<j))

Swapping elements may also cost more.
Index had to carry along, to break ties if needed.

swap(a[i], a[j])      → swap({a[i],i}, {a[j],j})

Another way to look at this, with index attached, all elements are different.
Sort stability issue is now moot.