Stable Sort

A StableSort is one where the initial order of equal items is preserved. Some sorting algorithms are naturally stable, some are unstable, and some can be made stable with care. Stability is important when we want to sort by multiple fields--for example, sorting a list of task assignments first by priority and then by assignee (in other words, assignments of equal priority are sorted by assignee). One easy way to do this is to sort by assignee first, then take the resulting sorted list and sort that by priority. This only works if the sorting algorithm is stable--otherwise, the sortedness-by-assignee of equal-priority items is not preserved.

For example, if sort the words "apple", "tree" and "pink" by length, then "tree", "pink", "apple" is a stable sort but "pink", "tree", apple" is not. MergeSort is a very common choice of StableSorts, achieved by favoring the leftmost item in each merge step (only if item_right < item_left put item_right first). RadixSort is another of the stable SortingAlgorithms.

CategoryAlgorithm