There are many sorting algorithms out there that are widely accepted: Insertion sort, quick sort, heap sort, merge sort, bucket sort… and so on and so forth. There are *a lot* of qualities of each sorting algorithm that allow you to choose what algorithm fits your requirements, but one of the sorting algorithm qualities I want to talk about in this post is **stability**.

## Sorting stability

Stability of a sorting algorithmn is the label that indicates whether or not it will preserve the order of two or more elements in the array **if they have equal sorting keys**. A sorting algorithm is **stable** if it preserves the order of multiple elements with the same keys. Conversely, a sorting algorithm is **unstable** if it cannot guarantee order preservation of multiple elements with equal keys.

An example in real life: There is a line of people that need to be ordered by age. If there are two people with the same age standing in line, the sorter would be using a stable approach if there is a guarantee that their order in line relative to each remains the same.

## When does stability matter?

Sorting stability is interesting by itself, but when do we care about it? We care in a situation when we *require* the output to have the guarantee of preserving order for duplicate keys.

### Example data

Let’s see another example and dissect it. Let’s say we have an array of data, where each element has two fields: `Name`

and `State`

. Here is a visual respresentation of the data:

### Requirement

Sort the data by state and then by name, so that the final data is ordered by state first and then by name.

### Approach

This data will be sorted twice so that the requirements can be met:

- Sort first by
`Name`

- Sort second by
`State`

The first sort by `Name`

doesn’t require a stable sorting algorithm, as the order for duplicate sorting keys (names) doesn’t matter. So in this case, we could do a heap sort (a naturally unstable sorting algorithmn) on this array by name.

The output from sorting by `Name`

is:

The second sort by `State`

is where it can get interesting. If we were to try a heap sort by `State`

, this is how we would setup our complete binary tree:

If we were to continue the heap sort by `State`

, we would end up with an array sorted like:

Yes, the array is sorted correctly by `State`

, but let’s see how the elements themselves transitioned:

The fact that elements with the same sorting key (`State`

) have overlapping sections to the destination array elements indicates that **their order was not preserved**, showing that this is a **unstable** sorting algorithmn.

### The solution

If we were to look back at the requirements, the heap sort by `State`

does not work: The output is sorted by `State`

but it is no longer sorted also by `Name`

within each `State`

.

Let’s try doing a second sort (by `State`

) with a naturally stable sorting algorithm: Merge sort. The output of the second sort if we were to use a merge sort (instead of a heap sort) would be:

Of course, `State`

is correctly sorted but now let’s see how the elments transitioned from being sorted by `Name`

to a merge sort by `State`

:

Now because we used a stable sorting algorithmn (merge sort) on `State`

, we preserved the order of elements with the same `State`

key value, giving us the desired output of a dataset that is sorted by state and then by name.

## Summary

Sorting algorithmns are a large part of computing, and understanding the behaviors of different algorithms will help in determining the right one for your requirements.