Search code examples
c++csortingqsortstable-sort

Make qsort stable just by modifying comparison?

Possible Duplicate:
Stabilizing the standard library qsort?

Is it possible to make qsort stable for ints just by modifying my comp op? That's my code. I'm using this on really small arrays of around 5-7 of size.

static int compare( const void *a, const void *b )
{
    const int A(*(const int*)(a));
    const int B(*(const int*)(b));

    return B - A;
}
Solution

  • If you are using C++, the stable_sort function is stable and have O(nlogn) performance.

    Otherwise, in-place quicksort is by its nature, unstable (I believe so). The trivial variant that use an extra array to store information is stable, however.

    I've used at least one version of qsort() that is unstable, because once I found that the result produced by qsort() and stable_sort() for a input case on my machine were different.