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

[Kuan-Wei Chiu <visitorckw@gmail.com>]

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.

Link: https://github.com/python/cpython/blob/main/Objects/listsort.txt

Best regards,
Kuan-Wei Chiu