[Bug libc/10672] New: qsort may not be a stable sort under memory exhaustion

[Bug libc/10672] New: qsort may not be a stable sort under memory exhaustion

[andersk at ksplice dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1342 bytes --]

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.

[Bug libc/10672] qsort may not be a stable sort under memory exhaustion

[andersk at ksplice dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 758 bytes --]


------- Additional Comments From andersk at ksplice dot com  2009-09-20 16:57 -------
Created an attachment (id=4219)
 --> (http://sourceware.org/bugzilla/attachment.cgi?id=4219&action=view)
Test program

This program exhausts all the available heap memory using malloc(), then
attempts to do a stable sort using qsort() as described by the glibc manual. 
As you can see from the output, some items with equal values have been
reordered:

…
0 0
0 0
10 4
10 2
10 3
20 1

If you comment the malloc() exhaustion loop, the sort becomes stable:

…
0 0
0 0
10 2
10 3
10 4
20 1


-- 


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.