From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 28454 invoked by alias); 11 Mar 2014 07:07:30 -0000 Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Post: List-Help: , Sender: glibc-bugs-owner@sourceware.org Received: (qmail 28395 invoked by uid 48); 11 Mar 2014 07:07:23 -0000 From: "allachan at au1 dot ibm.com" To: glibc-bugs@sourceware.org Subject: [Bug manual/10672] qsort may not be a stable sort under memory exhaustion Date: Tue, 11 Mar 2014 07:07:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: glibc X-Bugzilla-Component: manual X-Bugzilla-Version: 2.10 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: allachan at au1 dot ibm.com X-Bugzilla-Status: NEW X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: unassigned at sourceware dot org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: cc Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 7bit X-Bugzilla-URL: http://sourceware.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-SW-Source: 2014-03/txt/msg00067.txt.bz2 https://sourceware.org/bugzilla/show_bug.cgi?id=10672 paxdiablo changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |allachan at au1 dot ibm.com --- Comment #3 from paxdiablo --- It's a well known trick that you can make an unstable sort like Quicksort into a stable one by adding an address to the comparison key as the most minor component. However, this must be the STARTING address of each element and must be populated before the sort proper starts with something like: for (int i = 0; i < sz; i++) elem[i].startaddr = &(elem[i]); By using the starting address as the most minor part of the key, the order of otherwise similarly-keyed elements will be preserved. Using the TRANSITORY address will not work and in fact will break the sort contract as sometimes a will be less than b and sometimes vice versa, depending on their current address in memory. So, yes, that section of the documentation is dead wrong and should be removed or fixed. And, in fact, qsort() is not REQUIRED to be stable as per the ISO C standard. If you WANT a stable sort, go grab a copy of Mergesort from somewhere. -- You are receiving this mail because: You are on the CC list for the bug.