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.

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?

  • 2
    Because not all computing problems work well under the constraint "You can only sort once!". Many data-keeping operations involve long-standing data collections that are queried time and again for different primary criteria. – Kilian Foth Dec 4 '18 at 7:32
  • @KilianFoth you should put that in an answer and elaborate on it – Braden Best Dec 4 '18 at 7:43
  • The quotes don't say that the standard implementation is unstable, but that the implementation may (i.e. is free to) use an instable algo. – Christophe Dec 4 '18 at 7:44
  • @Christophe I realize that; my wording was ambiguous. Edited. – Braden Best Dec 4 '18 at 7:48
  • 1
    Your statement that you can put all the criteria in the comparison function makes a very strong assumption: namely that you know all the criteria. Imagine, you want to sort a list of students by school year. There will be many students who compare equal. The list of students is pre-sorted according to some criteria that you don't know. You would like to preserve this ordering within the age groups because there is probably some reason for why they are ordered this way. – Jörg W Mittag Dec 4 '18 at 8:47
8

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.

  • I think what I'm having trouble understanding is, in that scenario, and I'm thinking from the perspective of a GUI like Windows Explorer, what justifies using stable sort over two clicks (when the user didn't indicate that they wanted the list sorted according to criteria other than by-name and by-<the last thing the user clicked>) instead of a faster sorting algorithm that may not be stable, combined with some clever use of comparators. In both cases, the end result is the same, but from my perspective, the latter case is both more cleanly sorted on every run, and is most likely faster. – Braden Best Dec 4 '18 at 8:26
  • @BradenBest because "faster" is not the most important metric by which to evaluate algorithms – Caleth Dec 4 '18 at 10:00
  • @BradenBest, a stable sort algorithm is not inherently slower than a non-stable algorithm. the stability of a sorting algorithm is more a characteristic of the internal workings of the algorithm than anything else. – Bart van Ingen Schenau Dec 4 '18 at 11:33
  • @BartvanIngenSchenau True. I was referring more to cases like, say, quick sort (unstable) vs merge sort (stable), which if I'm not mistaken are some of the most common low-time-complexity sorting algorithms. – Braden Best Dec 4 '18 at 18:41
  • @BradenBest Sorting by multiple columns using multiple clicks works because it's a stable sort! – immibis Dec 12 '18 at 2:17
6

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:

enter image description here

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.

  • Not necessarily. If the user end of sorting is simple enough that it can be input by clicking a column header, then the developer can trivially implement all of the comparators for those as their own functions, and then implement meta-comparators, which take two comparators and compose from them an entirely new comparator. Plus, in every GUI of that sort that I've ever used, clicking one column automatically de-selects the other, and that column's criteria is used as the primary criterion while by-name is always the secondary criterion. No user-end programming knowledge required. – Braden Best Dec 4 '18 at 7:21
  • case in point, the example you show can easily be implemented with a single sorting pass, precisely as demonstrated in the question. – Braden Best Dec 4 '18 at 7:21
  • 3
    @BradenBest, with the "sort on column click" example, you can not prevent the multiple invocations to sort(). As a user, when I click the column header, I expect the data to be sorted according to that column 'immediately'. When I click the next column header 5 minutes later, then the data should be re-sorted at that time, according to what appears to be a stable sort (which can be achieved with a stable sort algorithm, or a composite comparator based on the two columns). But the data needs to be sorted twice anyway. – Bart van Ingen Schenau Dec 4 '18 at 7:33
  • 1
    If we get all intricate in performance, then there might even be a case where a decent optimized stable sort might outperform an unstable algorithm if the data representation of the fields are parallel, the output is something like indices (not a mutated version of the original data), and the comparator that would otherwise be required would have to inspect so many disparate fields. That's going to outer space though and benchmark contest territory. I'm just like, okay maybe it can be argued as laziness, but if the algorithm suffices and the resulting output [...] – Dragon Energy Dec 4 '18 at 7:55
  • 4
    Cheers. Well, I kind of want to avoid getting too into performance in the anwer because it kind of smells bad if we're talking about the particular column-sorting GUI context I mentioned. And there's so many ways to skin the cat and there's much more to consider than Big-O here when it comes to sorting performance. I actually brought this up just to illustrate how complex we can get with this stuff if we don't want to waste any user-end resources and consider any such waste lazy. – Dragon Energy Dec 4 '18 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.