c - 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

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.