[PATCH] stdlib: Reinstate stable mergesort implementation on qsort

[Zack Weinberg]

On Wed, Dec 6, 2023, at 3:22 PM, Adhemerval Zanella wrote:
...
> The drawback is mergesort requires O(n) extra space, and since it is
> allocated with malloc the function is AS-signal-unsafe.  It should be
> feasible to change it to use mmap, although I am not sure how urgent
> it is.  The heapsort is also nonstable, so programs that require a
> stable sort would still be subject to this latent issue.

It might be worthwhile investigating "block sort" aka "grail sort", which
is merge sort modified to be in-place and stable via clever reshuffling of
the input array.  For experimental purposes we could drop in either of
these implementations (one is Unlicense and the other is MIT):

https://github.com/BonzaiThePenguin/WikiSort
https://github.com/HolyGrailSortProject/Rewritten-Grailsort

zw