WTF is Stability in Sorting Algorithms?

“person hands on laptop computer” by rawpixel on Unsplash

A stable sort is one which preserves the original order of the input set, where the [unstable] algorithm does not distinguish between two or more items.

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

Further background: A ‘stable’ sorting algorithm keeps items in the same sorting key in order. For example, we have a list of 5-letter words:

peach
straw
apple
spork

A stable-sort that sorts by first letter of each word results in:

apple
peach
straw 
spork

In an unstable sort, straw or spork may be interchanged, but in a stable sort, they stay in the same relative positions.

Some stable sorting algorithms are:

• Insertion Sort
• Merge Sort
• Bubble Sort
• Tim Sort
• Counting Sort

Examples of unstable sorting algorithms are:

• Heap Sort
• Selection Sort
• Shell Sort
• Quick Sort

Interested in what you see here? Check out this cool visualization of different sorting algorithms.