Re: [PATCH] manual: Correct guarantee about pointers compared by qsort()

[Rich Felker <dalias at libc dot org>]

On Thu, Dec 11, 2014 at 06:00:18PM -0500, Anders Kaseorg wrote:
> On Thu, 11 Dec 2014, Rich Felker wrote:
> > > -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.
> > > +Although the object addresses passed to the comparison function lie
> > > +within the array, they need not correspond with the original locations
> > > +of those objects, because the sorting algorithm may swap around
> > > +objects in the array before making some comparisons.  The only way to
> > > +perform a stable sort with @var{qsort} is to first augment the objects
> > > +with a monotonic counter of some kind.
> > 
> > I think "the only way" is mistaken.
> 
> Note that the second sentence is unchanged in this patch.  The goal of 
> this patch is to fix an incorrect claim in the first sentence.

Sorry, I missed that.

> > Note that another way, often optimal in time anyway due to the smaller 
> > amount of data to be moved, is to create a new array of pointers to 
> > objects in the original array.  Then the array of pointers can be sorted 
> > using the address (not the address of the pointer, but the address 
> > stored in the pointer) as a factor,
> 
> Thatâs just another way to augment the objects with a monotonic counter, 
> where the monotonic counter is the address.
> 
> > and then the objects in the original array can be moved into the 
> > resulting order if desired (often it's not needed to do so anyway).
> 
> And this means using an additional nontrivial algorithm outside of qsort.  
> So Iâm not sure it counts as a way to âperform a stable sort with 
> @var{qsort}â.
> 
> Anyway, the reason the second sentence is there at all is to explicitly 
> contradict an incorrect recipe for stable qsort in previous versions of 
> the manual (https://sourceware.org/bugzilla/show_bug.cgi?id=10672).  If 
> you imagine youâre a programmer who wants to do a stable sort, and search 
> the web for related keywords, you find the current version of the manual 
> http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html 
> (which actually still contains that incorrect claim, but will be fixed 
> with the next release), along with some previous versions of the manual 
> (which will probably never be updated).  So I think itâs important that 
> the current version lets the programmer easily decide that the previous 
> version was wrong.
> 
> If youâd still like the second sentence changed, can I suggest doing it in 
> a separate patch?

Thanks for the detailed explanation. In that case I think it's best to
just keep the emphasis on the wrongness of that approach. The text
could perhaps be improved but it's not high-importance IMO. I was
working based on the wrong assumption that it was newly proposed text.

Rich