Why is stability considered a desirable trait of a sorting algorithm?

Question

The common argument for stability in a sorting algorithm typically involves an example where a list is sorted by two criteria. For example:

1,4,5,7,2,6,8,9,15,65,24,27
sort by evenness/oddness and then by value
2,4,6,8,24,1,5,7,9,15,27,65

The claim is that by choosing a stable sorting algorithm, you can sort this list twice--by value and then by evenness--and you will then have the list sorted as you had wanted.

I couldn't disagree more with this ideology, though. First of all, the sorting is done backwards (value, evenness, where evenness is the primary criterion), which is unintuitive. Second of all, by doing this, you are calling sort() twice.

Now let's take a look at some documentation. We have C's qsort(3) and JavaScript's Array.prototype.sort. Both of these functions, as far as I know, implement unstable sorting algorithms...

If two members compare as equal, their order in the sorted array is undefined.

and

If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.

...and both accept a function as an argument. This function is what I believe is called a comparator--a function that takes two values A and B, and returns -1, 0, or 1 depending on whether A is considered respectively "less than", "equal to" or "greater than" B, based on whatever arbitrary criteria the implementer chooses.

That said, what I have found is that no matter what I throw at the respective sorting functions, whether I implement them myself, or use the one from the standard library, is that stability has absolutely no bearing on the outcome of the sort when the sorting function is used correctly.

Let's use C's qsort as an example. qsort implements quick sort, and is known to be unstable.

If two members compare as equal, their order in the sorted array is undefined.

To clarify, this doesn't mean that the implementation is unstable per se. What it means is that stability is not guaranteed, so relying on those semantics is a very bad idea. Which is close enough.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INT(p) \
    ( *((int *)(p)) )

#define ISEVEN(p) \
    (INT(p) % 2 == 0)

void
randomize(int *list, size_t len)
{
    for(size_t i = 0; i < len; ++i)
        list[i] = rand() % (len * 10);
}

void
printlist(int *list, size_t len)
{
    for(size_t i = 0; i < len; ++i)
        printf("%i, ", list[i]);

    putchar('\n');
}

int
by_even(void const *a, void const *b)
{
    return (ISEVEN(a) && !ISEVEN(b)) ? (-1) : (ISEVEN(b) && !ISEVEN(a));
}

int
by_value(void const *a, void const *b)
{
    return (INT(a) < INT(b)) ? (-1) : (INT(a) > INT(b));
}

int
by_even_and_value(void const *a, void const *b)
{
    return by_even(a, b) != 0 ? by_even(a, b) : by_value(a, b);
}

int
main(void)
{
    static size_t const listsz = 20;
    int list[listsz];

    srand(time(NULL));
    randomize(list, listsz);
    printlist(list, listsz);
    qsort(list, listsz, sizeof list[0], by_even_and_value);
    printlist(list, listsz);

    return 0;
}

And this is the output:

$ cc qsort.c
$ ./a.out
100, 111, 12, 122, 96, 50, 52, 96, 173, 125, 135, 173, 78, 144, 108, 60, 75, 116, 24, 180,
12, 24, 50, 52, 60, 78, 96, 96, 100, 108, 116, 122, 144, 180, 75, 111, 125, 135, 173, 173,

So putting all of the sorting criteria inside the comparator and sorting once gave me the sorted list I wanted. It only took me one sort, and the criteria was able to be given in-order (even first, value second).

As this renders stability ostensibly irrelevant to the outcome, why should one be concerned with the stability of a sorting algorithm?

Answer 1

The common argument for stability in a sorting algorithm typically involves an example where a list is sorted by two criteria. For example:

1,4,5,7,2,6,8,9,15,65,24,27
sort by evenness/oddness and then by value
2,4,6,8,24,1,5,7,9,15,27,65

The claim is that by choosing a stable sorting algorithm, you can sort this list twice--by value and then by evenness--and you will then have the list sorted as you had wanted.

This example seems to have seriously mislead you with regards to what "stable sort" implies.

A better example would be

Given a numerically ordered list of numbers: 1,2,4,5,6,7,8,9,15,24,27,65
When you sort this list by evenness/oddness with a stable sorting algorithm, then the sub-list of even and odd numbers will still be numerically ordered: 2,4,6,8,24,1,5,7,9,15,27,65.

A stable sorting algorithm does not imply (or require) that the sort() function gets called twice. Getting the input numerically ordered is not part of the stable sorting algorithm, but rather a tool to show the stability property of the sorting algorithm.

A stable sorting algorithm only states that elements that are equal according to the comparator are kept in the same relative order as in the input. This can be shown with input that is pre-sorted according to a different criterion, or with more complex data structures where not all fields contribute to the sorting, but those more complex data structures make for a more difficult presentation in an example.

In practice, a stable sorting algorithm is most useful when you need to re-order user-facing data, because most end-users expect that kind of behavior.

Answer 2

Second of all, by doing this, you are calling sort() twice.

I'm not sure if this is the most complete answer but sometimes it's useful to sort multiple times in separate passes for user-end requirements. It might seem computationally inefficient but sometimes it makes sense from the user-end perspective.

A common example is when you see GUIs that are laid out like a grid/table with columns you can click on to sort the data by a particular field, like this:

In those cases it's not necessarily so practical for the user to be required to specify the precise order of multiple columns to sort as keys and sub-keys and sub-sub-keys and so on with a single sorting pass using a comparator which compares multiple fields at once to produce the desired ordering and sub-ordering and so forth (or for the software to try to remember the previous columns clicked on to generate the appropriate comparator). There it can be a lot simpler to do a separate sorting pass with each click of a column and use a stable sort as a way to minimally disrupt the relative order of the previous sort(s) the user requested by clicking.

I tend to think of the stable sort as a "less disruptive" sort which is often a bit more expensive to compute but has the benefit of maintaining some relative sub-ordering of the original data. And sometimes it's just very practical in code at least to do that in separate passes instead of one uber sorting pass with the appropriate comparator which gives exactly the desired results in one go.

So that's one example where it might be more useful to just stable sort to give more predictable and minimally disruptive results than try to do it all in one sorting pass just by the nature of the user-end design.