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

["Zack Weinberg" <zack@owlfolio.org>]

On Wed, Dec 6, 2023, at 7:51 AM, Adhemerval Zanella Netto wrote:
> On 06/12/23 07:21, Florian Weimer wrote:
>> * Zack Weinberg:
>>>
>>> Before you go any further with this patch series I think we need to
>>> decide whether our backward compatibility constraints mean our qsort
>>> has to be a stable sort.  If so, we should make it *always* be a
>>> stable sort and write that into the documentation, and that would
>>> mean junking the entire heapsort implementation.
>>
>> That makes sense, although there might not exist an in-place sorting
>> algorithm that takes constant extra space regardless of element
>> count and element size and has reasonable performance.  Maybe we
>> could say, “stable if element size is less than 1024 bytes” or
>> something like that.

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.

(That said, I still think we should give that "block exchange mergesort"
algorithm I dug up the other week a try.  I might have time early in
January to put a patch set together.)

zw