about summary refs log tree commit diff
path: root/manual/search.texi
diff options
context:
space:
mode:
authorAnders Kaseorg <andersk@MIT.EDU>2014-07-02 21:17:50 -0400
committerOndřej Bílka <neleai@seznam.cz>2014-12-10 16:24:44 +0100
commitf5f46d51f75083e27fae79cee6cd7707888faba3 (patch)
tree5a31623e034dfa63c27d713ec8b189e380cde710 /manual/search.texi
parentb987c89126b84b06c22b13c2827499bc9d9e5e88 (diff)
downloadglibc-f5f46d51f75083e27fae79cee6cd7707888faba3.tar.gz
glibc-f5f46d51f75083e27fae79cee6cd7707888faba3.tar.xz
glibc-f5f46d51f75083e27fae79cee6cd7707888faba3.zip
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>
Diffstat (limited to 'manual/search.texi')
-rw-r--r--manual/search.texi9
1 files changed, 4 insertions, 5 deletions
diff --git a/manual/search.texi b/manual/search.texi
index 509a54313a..8aff57433a 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