Why is an "unstable sort" considered bad

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?

---

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).

---

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.

---

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.

---

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.