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: Florian Weimer <fweimer at redhat dot com>
- To: Anders Kaseorg <andersk at MIT dot EDU>, libc-alpha at sourceware dot org
- Date: Tue, 01 Jul 2014 10:41:07 +0200
- 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>
On 07/01/2014 10:13 AM, Anders Kaseorg wrote:
Under certain conditions on the size of the array and its items,
qsort() may fall back to an in-place quicksort if it cannot allocate
memory for a temporary array with malloc(). This algorithm is not a
stable sort even if the comparison function is written in the
described manner.
-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.
I would suggest to remove the entire paragraph instead, or perhaps a
warning that the pointers with which the comparison function is called
do not necessarily have to reside within the input array.
--
Florian Weimer / Red Hat Product Security