What does it mean for a sorting algorithm to be “stable”?
A sorting algorithm is stable if it preserves the order of duplicate keys. OK, fine, but why should this be important? Well, the question of “stability” in a sorting algorithm arises when we wish to sort the same data more than once according to different keys. Sometimes data items have multiple keys. For example, perhaps a (unique) primary key such as a social insurance number, or a student identification number, and one or more secondary keys, such as city of residence, or lab section. And we may very well want to sort such data according to more than one of the keys. The trouble is, if we sort the same data according to one key, and then according to a second key, the second key may destroy the ordering achieved by the first sort. But this will not happen if our second sort is a stable sort.
