Difference between Stable and Unstable Sorting Algorithm?

Javin PaulJune 28th, 2017Last Updated: June 27th, 2017

3 1,478 3 minutes read

Recently in one on the interview, after some initial questions about sorting algorithms e.g. how do you write QuickSort or difference between QuickSort and MergeSort, the interviewer asked about do you understand the difference between stable and unstable sorting algorithm? This question was new to my reader, so he says, Sorry, never heard about that. The story ended there, and Interviewer moved on to next question but like many of us, my reader went on to find more about unanswered questions and ultimately he asks me what is the meaning of a stable and unstable sorting algorithm? Some of you might be heard about it and many of you might not know about this distinction, I’ll try to answer this question in this article.

A sorting algorithm is said to be stable if it maintains the relative order of numbers/records in the case of tie i.e. if you need to sort 1 1 2 3 then if you don’t change order of those first two ones than your algorithm is stable, but if you swap them then it becomes unstable, despite overall result or sorting order remain same.

This difference becomes more obvious when you sort objects e.g. sorting key value pairs by keys. In the case of a stable algorithm, the original order of key value pair is retained as shown in the following example.

Actually, Interviewer might ask that question as a follow-up of quicksort vs merge sort if you forget to mention those concepts. One of the main difference between quicksort and mergesort is that formerly is unstable but merge sort is a stable sorting algorithm.

Stable vs Unstable Algorithm

Suppose you need to sort following key-value pairs in the increasing order of keys:

INPUT: (4,5), (3, 2) (4, 3) (5,4) (6,4)

Now, there is two possible solution for the two pairs where the key is same i.e. (4,5) and (4,3) as shown below:

OUTPUT1: (3, 2),  (4, 5),  (4,3),  (5,4),  (6,4)

OUTPUT2: (3, 2),  (4, 3),  (4,5),  (5,4),  (6,4)

The sorting algorithm which will produce the first output will be known as stable sorting algorithm because the original order of equal keys are maintained, you can see that (4, 5) comes before (4,3) in the sorted order, which was the original order i.e. in the given input, (4, 5) comes before (4,3) .

On the other hand, the algorithm which produces second output will know as an unstable sorting algorithm because the order of objects with the same key is not maintained in the sorted order. You can see that in the second output, the (4,3) comes before (4,5) which was not the case in the original input.

Now, the big question is what are some examples of stable and unstable sorting algorithms? Well, you can divide all well-known sorting algorithms into sorted and unsorted. Some examples of stable algorithms are Merge Sort, Insertion Sort, Bubble Sort and Binary Tree Sort. While, QuickSort, Heap Sort, and Selection sort are the unstable sorting algorithm.

If you remember, Collections.sort() method from Java Collection framework uses iterative merge sort which is a stable algorithm. It also does far fewer comparison than NLog(N) in case input array is partially sorted.

If you are interested in learning more about this topic, I suggest you read a good book on Data Structure and Algorithms e.g. Introduction to Algorithms by Thomas H. Cormen.

It’s said that a picture is worth more than 1000 words, so let’s see an image which explains how stable and unstable sort works:

That’s all about the difference between stable and unstable sorting algorithm. Just remember, that if the original order of equal keys or number is maintained in the sorted output then the algorithm is known as sorting algorithm. Some popular examples of stable sorting algorithms are merge sort, insertion sort, and bubble sort.