Sourceware Bugzilla – Bug 10672
qsort may not be a stable sort under memory exhaustion
Last modified: 2012-12-19 10:45:58 UTC
The glibc documentation makes this claim:
“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.
Created attachment 4219 [details]
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
If you comment the malloc() exhaustion loop, the sort becomes stable:
This is a bug in the manual. The text about using the address as part of the comparison function is not only ineffective but actually results in undefined behavior due to violation of the requirements on comparison functions. It should just be removed.