[PATCH v2] stdlib: Reinstate stable mergesort implementation on qsort

Alexander Monakov amonakov@ispras.ru
Fri Jan 12 11:50:22 GMT 2024


On Fri, 12 Jan 2024, Florian Weimer wrote:

> * Adhemerval Zanella:
> 
> > diff --git a/manual/search.texi b/manual/search.texi
> > index a550858478..5691bf2f2b 100644
> > --- a/manual/search.texi
> 
> > @@ -199,8 +199,9 @@ Functions}):
> >  The @code{qsort} function derives its name from the fact that it was
> >  originally implemented using the ``quick sort'' algorithm.
> >  
> > +The implementation of @code{qsort} in this library might not be an
> > +in-place sort and might thereby use an extra amount of memory to store
> > +the array.
> >  @end deftypefun
> 
> I'd appreciate if a native speaker could have look at this.

I think this should be rephrased since C qsort is not allowed to be observably
out-of-place, although in practice this is a pedantic requirement and only
restricts library implementations without, seemingly, yielding anything useful
for callers of qsort. To be clear, I am referring to C11 7.22.5 p2:

     The implementation shall ensure that the second argument of the comparison
     function (when called from bsearch), or both arguments (when called from
     qsort), are pointers to elements of the array [+ footnote 302].

I'd suggest to avoid the possible ambiguity and instead say something like
"the implementation of qsort attempts to allocate auxiliary storage and
use the merge sort algorithm, without violating C standard requirement that
arguments passed to the comparison function point within the array".

Alexander


More information about the Libc-alpha mailing list