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

[Florian Weimer <fweimer@redhat.com>]

* Kuan-Wei Chiu:

> On Sun, Dec 17, 2023 at 10:42:17AM -0500, Zack Weinberg wrote:
>> 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.)
>
> Additionally, if we're open to exploring non-in-place options, I think
> Timsort might be worth considering. It's widely adopted, including in
> Python and Android, serving as a stable hybrid sorting algorithm.
> Timsort is an adaptive sort algorithm that operates in O(n) time when
> the input is already sorted and maintains a worst-case time complexity
> of O(n log n), similar to mergesort. I'd be happy to prepare a patch
> for Timsort next month if needed.

I think we really want to get rid of that malloc in qsort.  This means
that we need something in-place-ish: we can throw a fair amount of stack
space at the problem (probably quite a bit more of the circa 1024 bytes
we use today), but not something that scales linearly with the size of
the input array.  We cannot not even even assume space for just one
temporary object on the stack, I think.

Thanks,
Florian