This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] manual: Remove incorrect claim that qsort() can be stabilized
- From: Anders Kaseorg <andersk at MIT dot EDU>
- To: "Alfred M. Szmidt" <ams at gnu dot org>
- Cc: libc-alpha at sourceware dot org
- Date: Wed, 2 Jul 2014 21:15:04 -0400 (EDT)
- Subject: Re: [PATCH] manual: Remove incorrect claim that qsort() can be stabilized
- Authentication-results: sourceware.org; auth=none
- References: <alpine dot DEB dot 2 dot 02 dot 1407010413160 dot 28890 at all-night-tool dot MIT dot EDU> <E1X1ttP-0003QC-Ps at fencepost dot gnu dot org>
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