A sort (sort algorithm or specific implementation) is called *stable* if the order of every two *equivalent* elements in the input is preserved in the output. (2 elements are "equivalent" if neither is larger than the other)

Stability is a desirable property. For one thing, a stable sort can be used to sort according to a primary key and a secondary key by sorting first by the secondary, then by the primary key. Without stability, the seconday key ordering could be destroyed by the second sort.

For instance, if we wish to sort all people by height, then by alphabetical order (for people of the same height), we could take them sorted in order of their names, and then apply a stable sort on their heights. 2 people can have the same height, so we want the second sort to keep them ordered by name.

Some sorts (like merge sort or bubble sort) can easily be made stable. Radix sort practically *has* to be stable, as it's exactly this type of "repeated sort". Other sorts, most notable quicksort are *unstable*! It is not known how to make quicksort stable.