From patchwork Thu Jul 3 01:17:50 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Anders Kaseorg X-Patchwork-Id: 1862 Received: (qmail 4318 invoked by alias); 3 Jul 2014 01:18:18 -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 4125 invoked by uid 89); 3 Jul 2014 01:18: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-3.mit.edu Date: Wed, 2 Jul 2014 21:17:50 -0400 (EDT) From: Anders Kaseorg To: Florian Weimer cc: libc-alpha@sourceware.org Subject: [PATCH v2] manual: Remove incorrect claim that qsort() can be stabilized In-Reply-To: <53B27423.2050903@redhat.com> Message-ID: References: <53B27423.2050903@redhat.com> 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 --- On Tue, 1 Jul 2014, Florian Weimer wrote: > 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. What do you think about this wording, then? (The problem is not actually about pointers residing outside the input array, because it happens that the algorithm where that occurs is stable. But I agree it’s worth mentioning too.) Anders manual/search.texi | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/manual/search.texi b/manual/search.texi index 509a543..8aff574 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -180,11 +180,10 @@ 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. +The addresses passed to the comparison function need not correspond with +the original location of the objects, and need not even lie within the +original array. 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