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.