From patchwork Tue Jul 1 08:13:55 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anders Kaseorg X-Patchwork-Id: 1830 Received: (qmail 23849 invoked by alias); 1 Jul 2014 08:14:04 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 23808 invoked by uid 89); 1 Jul 2014 08:14:02 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.6 required=5.0 tests=BAYES_00, CLAIM_SUBJECT, RCVD_IN_DNSWL_LOW, SPF_PASS, T_RP_MATCHES_RCVD autolearn=no version=3.3.2 X-HELO: dmz-mailsec-scanner-1.mit.edu Date: Tue, 1 Jul 2014 04:13:55 -0400 (EDT) From: Anders Kaseorg To: libc-alpha@sourceware.org Subject: [PATCH] manual: Remove incorrect claim that qsort() can be stabilized Message-ID: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 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. Fixes #10672. Signed-off-by: Anders Kaseorg --- manual/search.texi | 12 +++++++----- 1 file changed, 7 insertions(+), 5 deletions(-) diff --git a/manual/search.texi b/manual/search.texi index 509a543..6390272 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -180,11 +180,13 @@ This can make a difference when the comparison considers only part of the elements. Two elements with the same sort key may differ in other respects. -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. Here is a simple example of sorting an array of doubles in numerical order, using the comparison function defined above (@pxref{Comparison