Stabilizing the standard library qsort?

Question

I'm assuming that the good old qsort function in stdlib is not stable, because the man page doesn't say anything about it. This is the function I'm talking about:

   #include <stdlib.h>
   void qsort(void *base, size_t nmemb, size_t size,
              int(*compar)(const void *, const void *));

I assume that if I change my comparison function to also include the address of that which I'm comparing, it will be stable. Is that correct?

Eg:

int compareFoos( const void* pA, const void *pB ) {
    Foo *pFooA = (Foo*) pA;
    Foo *pFooB = (Foo*) pB;

    if( pFooA->id < pFooB->id ) {
        return -1;
    } else if( pFooA->id > pFooB->id ) {
        return 1;
    } else if( pA < pB ) {
        return -1;            
    } else if( pB > pA ) {
       return 1;
    } else {
       return 0;
    }
}

Answer 1

First thing that comes to mind: make sure you understand the sense of the sort and the storage conventions of your architecture.

But yeah, I think so.^W^W^W.

Never mind. I see in Pax's answer that quicksort is intrinsically unstable. Oh, well, it was a good idea.

---

BTW--- there is no requirement that qsort actually use quicksort. I've read that many real world implementations use a merge sort instead...

The Mac OS X manpage for qsort specifies that the function is not stable but that is is quicksort (i.e. " a variant of partition-exchange sorting; in particular, see D.E. Knuth's Algorithm Q").

Mac OS X offers a separate library function for mergesort which is stable. Check your local documentation, or implement your own.

Answer 2

http://www.manpagez.com/man/3/qsort/ explicitly states that qsort is not stable, so you cannot assume that it will be stable on every platform.

Edit: on second thought, I'm not so sure anymore that your code is correct. qsort might shuffle objects around before calling your compare function. Remaining question: do objects that are in order ever get swapped out of order by the quicksort algorithm? I'm too tired to risk thinking about this right now and giving you a wrong answer...

Answer 3

No, you cannot rely on that unfortunately. Let's assume you have the array (two fields in each record used for checking but only first field used for sorting):

BBBB,1
BBBB,2
AAAA,3

Quicksort may compare BBBB,1 with AAAA,3 and swap them, giving:

AAAA,3
BBBB,2
BBBB,1

If the next step were to compare BBBB,2 with BBBB,1, the keys would be the same and, since BBBB,2 has an address less than BBBB,1, no swap will take place. For a stable sort, you should have ended up with:

AAAA,3
BBBB,1
BBBB,2

The only way to do it would be to attach the starting address of the pointer (not its current address) and sort using that as well as the other keys. That way, the original address becomes the minor part of the sort key so that BBBB,1 will eventually end up before BBBB,2 regardless of where the two BBBB lines go during the sorting process.