This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug libc/10672] New: qsort may not be a stable sort under memory exhaustion
- From: "andersk at ksplice dot com" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 20 Sep 2009 16:52:31 -0000
- Subject: [Bug libc/10672] New: qsort may not be a stable sort under memory exhaustion
- Reply-to: sourceware-bugzilla at sourceware dot org
The glibc documentation makes this claim:
http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html
?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.?
However, 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.
I will attach a simple test program that demonstrates this.
--
Summary: qsort may not be a stable sort under memory exhaustion
Product: glibc
Version: 2.10
Status: NEW
Severity: normal
Priority: P2
Component: libc
AssignedTo: drepper at redhat dot com
ReportedBy: andersk at ksplice dot com
CC: glibc-bugs at sources dot redhat dot com
http://sourceware.org/bugzilla/show_bug.cgi?id=10672
------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.