display | more...

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.

Log in or register to write something here or to contact authors.