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.
Created attachment 4219 [details] 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
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.
It's a well known trick that you can make an unstable sort like Quicksort into a stable one by adding an address to the comparison key as the most minor component. However, this must be the STARTING address of each element and must be populated before the sort proper starts with something like: for (int i = 0; i < sz; i++) elem[i].startaddr = &(elem[i]); By using the starting address as the most minor part of the key, the order of otherwise similarly-keyed elements will be preserved. Using the TRANSITORY address will not work and in fact will break the sort contract as sometimes a will be less than b and sometimes vice versa, depending on their current address in memory. So, yes, that section of the documentation is dead wrong and should be removed or fixed. And, in fact, qsort() is not REQUIRED to be stable as per the ISO C standard. If you WANT a stable sort, go grab a copy of Mergesort from somewhere.
Created attachment 7665 [details] Remove incorrect claim from manual
(In reply to Anders Kaseorg from comment #4) > Created attachment 7665 [details] > Remove incorrect claim from manual Could you post this patch to the mailing list for review, please? I think it is best to remove the problematic wording altogether, not attempting to describe the past behavior of the implementation.
Posted: https://sourceware.org/ml/libc-alpha/2014-07/msg00002.html
fixed.