Re: [PATCH] stdlib: Optimize number of calls to comparison function

[Florian Weimer <fweimer@redhat.com>]

* Zack Weinberg:

> It occurred to me late last night that *any* in-place sorting algorithm
> that operates on an array, can be made stable with no additional storage
> cost, by using each element's address as a tiebreaker for the comparison
> function.  It *doesn't* need to be the element's original address -- all
> that matters is that for every pair of elements that compare equal, the
> sorting algorithm preserves the < relation for their addresses across
> all swaps, which should happen naturally if address-< is used as a
> tiebreaker for comparisons.

It's not as simple as that because we might have A < B, so we can move A
to a lower address than B, but at the same time time, we must make sure
that we do not move it past an element C with A == C, otherwise the
result of the tie-breaking address comparison changes.  I haven't really
thought about it, but I suspect it's possible to do for some of the
quadratic algorithms, but quicksort and heapsort—not so much.

Thanks,
Florian