qsort_r()
Douglas Bagnall
douglas.bagnall at catalyst.net.nz
Sat Mar 24 04:53:37 UTC 2018
On 24/03/18 14:15, Timur I. Bakeyev via samba-technical wrote:
> On unrelated note I want to remind everyone that at least for FreeBSD:
>
> The algorithms implemented by qsort(), qsort_r(), and heapsort() are _not_
> stable, that is, if two members compare as equal, their order in the
> sorted array is undefined.
>
> We've been bitten by this at least once. So something to keep in mind...
This is actually also true with linux/glibc under memory pressure, where qsort()
et. al. abandon their surreptitious attempts at mergesort:
https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/msort.c;h=266c2538c07e86d058359d47388fe21cbfdb525a;hb=refs/heads/master#l213
The documentation explicitly disclaims sort stability.
Douglas
More information about the samba-technical
mailing list