14

Just wondering if someone could explain why an "unstable sort" is considered bad? Basically I don't see any situations where it would really matter. Could anyone care to provide one?

Maxim Gershkovich
  • 45,951
  • 44
  • 147
  • 243
  • 6
    Who considers it "bad"? Do you have a quote or a reference or a link? It would help to have some context for this kind of value judgement. – S.Lott May 11 '11 at 03:18
  • possible duplicate of [What is the benefit for a sort algorithm to be stable?](http://stackoverflow.com/questions/808617/what-is-the-benefit-for-a-sort-algorithm-to-be-stable) – nawfal Jun 13 '14 at 15:59

4 Answers4

26

If you have a GUI that allows people to sort on individual columns by clicking on that column, and you use a stable sort, then people who know can get a multi-column sort on columns A,B,C by clicking on columns C,B,A in that order. Because the sort is stable, when you click on B any records with equal keys under B will still be sorted by C so after clicking on B the records are sorted by B, C. Similarly, after you click on A, the records are sorted by A, B, C.

(Unfortunately, last time I tried this on some Microsoft product or other, it looked like it didn't use a stable sort, so it's not surprising this trick is not better known).

mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • 2
    Nice example. But do you mean to say that there's a Microsoft product that isn't stable? Shocking! :) – Ted Hopp May 11 '11 at 17:15
  • Glad I read this. it didn't occur to me that such a thing wouldn't use a reliable sort. – Michael Wilson Aug 14 '12 at 14:34
  • But can't an unstable sort always be made stable by adding a rownum/index or some other kind of unique counter as the last element in a composite sort key? Unless I'm missing something, adding that seems trivial. – Drakarah Feb 14 '15 at 15:53
  • @drake7707 You can indeed create a stable sort from an unstable sort in this way. It would be nice if sorting APIs were always written with this use case in mind, and GUIs always used this to provide stable sorts to the user. Alas, this does not always happen. – mcdowella Feb 23 '15 at 07:06
5

Imagine that you wanted to organize a deck of cards. You could sort first by suit, then by numeric value. If you used a stable sort, you'd be done. If you used an unstable sort, then they'd be in numeric order, but the suits would be all messed up again. There are lots of equivalent situations that come up in real development problems.

Ernest Friedman-Hill
  • 80,601
  • 10
  • 150
  • 186
  • I don't think this is a really good comparison, because both suit and number should be taken into account for any comparison function. Also note that if you'd use a stable sorting method for this, you'd have to sort by number and then suit, but not the other way. – Billy ONeal May 11 '11 at 03:15
  • 1
    I am not following you, @Billy. First, you'd need a comparison function that took both things into account if, and only if, you didn't have a stable sort. Otherwise you could have a simple comparison function of the type that, in dynamic languages, can be written generically to sort by some property by name. And second, you seem to feel that there's only one way to organize a deck of cards. I assure you, "organize" can be interpreted in multiple ways. – Ernest Friedman-Hill May 11 '11 at 04:02
4

There are just a few cases where you need a sort algorithm that's stable. An example of this is if you're implementing something like a Radix sort, which depends on the idea that the comparison sorting algorithm used as the building block is stable. (Radix sort can operate in linear time, but it's inputs are more restricted than comparison sorting algorithms. (Comparison sorts require O(n lg n) time))

It's not necessarily that a sort that is unstable is "bad"; it's more that a sort that is stable is "desirable in some cases". That's why programming languages, e.g. C++'s Standard Template Library, provide both -- e.g. std::sort and std::stable_sort -- which allow you to specify when you need stability, and when you don't.

Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
  • 1
    No idea who downvoted, but I would guess they found your example of using a stable sort to perform another sort is kinda atypical. – user541686 Aug 14 '12 at 10:35
  • "which depends on the idea that the comparison[-based] sorting algorithm used as the building block is stable" - what are you talking about? What's the 'building block' of radix sort and why does it need to be stable? Regardless of whether or not that actually makes sense, a sort isn't exactly a good example of why a stable sort is desirable in some cases. – Bernhard Barker Dec 01 '13 at 18:39
  • @Dukeling: Because a radix sort sorts each digit in a number (digits separated by radix, hence radix sort), and relies on the stability of the underlying sort for correct behavior. (Otherwise, sorting by one digit could destroy the results from sorting another digit) As for "not a good example", you are entitled to your opinion. – Billy ONeal Dec 02 '13 at 01:13
  • Oh right, you mentioning comparison-based sorting might've thrown me a bit. [Wikipedia](http://en.wikipedia.org/wiki/Radix_sort#Definition) suggests bucket sort or counting sort, neither of which are comparison-based. – Bernhard Barker Dec 02 '13 at 15:11
  • +1 Odd that your example of radix sort is downvoted when the highly upvoted accepted answer is just a real-world example of the same concept. – Paul Bellora Feb 02 '14 at 16:17
1

Because they can do better than I could do...from Developer Fusion:

There are two kinds of sort algorithms: "stable sorts" and "unstable sorts". These terms refer to the action that is taken when two values compare as equal. If you have an array T0..size with two elements Tn and Tk for n < k, and these two elements compare equal, in a stable sort they will appear in the sorted output with the value that was in Tn preceding Tk. The output order preserves the original input order. An unstable sort, by contrast, there is no guarantee of the order of these two elements in the output.

Note that sorting algorithms like quick sort are not stable or unstable. The implementation will determine which it is.

In any case, stable is not necessarily better or worse than unstable - it's just that sometimes you need the guarantee of the order to two equal elements. When you do need that guarantee, unstable would not be suitable.

JasCav
  • 34,458
  • 20
  • 113
  • 170
  • 2
    I think the OP understands what the difference between the two kinds of sorts are. He's asking why a sort which is unstable would be "bad" -- which implies that (s)he knows what makes a sort unstable. – Billy ONeal May 11 '11 at 03:23
  • @Billy - Very true. I guess, for the purposes of a better answer, I wanted to spell out what it is so I could then say my final paragraph - one is not necessarily "bad" or "good" except in a specific case. – JasCav May 11 '11 at 03:24