This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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(-)

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
-- 
2.0.0


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]