diff mbox

manual: Remove incorrect claim that qsort() can be stabilized

Message ID alpine.DEB.2.02.1407010413160.28890@all-night-tool.MIT.EDU
State Superseded
Headers show

Commit Message

Anders Kaseorg July 1, 2014, 8:13 a.m. UTC
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 <andersk@mit.edu>
---
 manual/search.texi | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

Comments

Florian Weimer July 1, 2014, 8:41 a.m. UTC | #1
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.
Alfred M. Szmidt July 1, 2014, 8:58 a.m. UTC | #2
-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.

Personally, I think this blurb should be put in the NEWS file not
here.  To some extent it is a user-visible change.
Anders Kaseorg July 3, 2014, 1:15 a.m. UTC | #3
On Tue, 1 Jul 2014, Alfred M. Szmidt wrote:
>    -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.
> 
> Personally, I think this blurb should be put in the NEWS file not
> here.  To some extent it is a user-visible change.

You understand that this is not a behavior change, right?  qsort has 
always behaved this way; this paragraph has never been correct.  We could 
just remove it (let me know if you want me to send such a patch), but I 
thought it might be worthwhile to say something to discourage any further 
propagation of whatever misconception led to its addition in the first 
place.

Anders
diff mbox

Patch

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