Stable sort

A stable sort is a sorting algorithm that does not change the relative order of elements that have equal key values. This is important for some algorithms (for example, radix sort).

Some common stable sorts are:

• bubble sort
• [bucket sort]?
• [counting sort]?
• merge sort
• radix sort

Many other sorting algorithms can be specially implemented to be stable sorts. One way of doing this is to artificially extend the key comparison, such that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original data order as a tie-breaker.