# Stable Sort

Jump to navigation
Jump to search

A sorting algorithm is called **stable** if it keeps elements with equal keys in the same relative order in the output as they were in the input.

For example, in the following input the two 4's are indistinguishable:

- 1,4
_{a},3,4_{b},2

And so the output of a stable sorting algorithm must be:

- 1,2,3,4
_{a},4_{b}

Bubble sort, merge sort, counting sort ,insertion sort are stable sorting methods. Most implementations of quicksort are not stable sorts.

Radix sorting is an important application of stable sorting: the observation is that if we want to sort elements by a composite key, such as (*year*, *month*, *day*), we may as well do three stable sorting passes on separate keys *day*, *month* and *year* (in that order), and get the same result.