Stable and Unstable Sorting Algorithms

April 20, 2022

Stable and Unstable Sorting Algorithms

While reading about different sorting algorithms you would have come across the terms stable sorting algorithms and unstable sorting algorithms. In this post we’ll see what is the difference between stable and unstable sorting algorithms.

Stable sorting algorithm

A sorting algorithm is said to be stable if the order of the same values in the output remains the same as in input array.

This is an example of stable sorting, element 12 appears twice at index 5 and at index 7. In the output array after sorting is done the order is maintained 12 which was at index 5 appears first and 12 which was at index 7 appears later.

Unstable sorting algorithm

In an unstable sorting algorithm the ordering of the same values is not necessarily preserved after sorting.

Here you can see that the ordering for the same element 12 is not maintained after sorting.

Stability with key, value pair

Application of stability becomes more important when we have key value pairs where keys can be duplicated.

For example suppose records with timestamps are stored in an array as they arrive, so the records are in order of the timestamp in the array. Now you want to sort on cities. If an unstable sort is used to do so the records for each city may not necessarily be in order by timestamp after the sort.