This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] manual: Remove incorrect claim that qsort() can be stabilized


On Tue, 1 Jul 2014, Alfred M. Szmidt wrote:
>    -If you want the effect of a stable sort, you can get this result by
>    -writing the comparison function so that, lacking other reason
>    -distinguish between two elements, it compares them by their addresses.
>    -Note that doing this may make the sorting algorithm less efficient, so
>    -do it only if necessary.
>    +Previous versions of this manual incorrectly claimed that you can get
>    +the effect of a stable sort by writing the comparison function to
>    +compare the element addresses as a last resort.  This does not work
>    +because, under certain conditions, @var{qsort} falls back to an in-place
>    +algorithm that compares some elements after moving them around in
>    +memory.  The only way to perform a stable sort with @var{qsort} is to
>    +first augment the objects with a monotonic counter of some kind.
> 
> Personally, I think this blurb should be put in the NEWS file not
> here.  To some extent it is a user-visible change.

You understand that this is not a behavior change, right?  qsort has 
always behaved this way; this paragraph has never been correct.  We could 
just remove it (let me know if you want me to send such a patch), but I 
thought it might be worthwhile to say something to discourage any further 
propagation of whatever misconception led to its addition in the first 
place.

Anders


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]