Difference between Stable and Unstable Sorting Algorithm?

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 stable and unstable. 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:

Difference between Stable and Unstable Sorting Algorithm

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. 

Further Reading

Thanks for reading this article. If you like this interview question and my explanation then please share with your friends and colleagues. If you have any question or feedback then please drop a comment. 


Ned Horvath said...

Minor nit: the sentence, "Well, you can divide all well-known sorting algorithms into sorted and unsorted." should end "...stable and unstable."
Another reference: Knuth, Art of Computer Programming v.3 is pretty comprehensive.
Finally, hashing, Moore's Law, and Map-Reduce have all but eliminated the need to ever sort anything. The motivation to sort is rapid search, and those technologies allow much more rapid search of dynamic datasets.
But I'm just an old curmudgeon, and I could be wrong. PS: my PhD thesis was finding an algorithm for stable sort in-place (no extra space) in O(nlogn). A VERY long time ago.

Javin Paul said...

Thanks for your valuable input @Ned, I'll will correct the typo. YEs, Knuth, Art of Computer Programming is very comprehensive and I really didn't read it end to end but its good book to refer any computer science concept. I mostly refer it for algorithms and data structure and it always offer something I don't know. Btw, didn't in place Mergesort is a O(nLogN) stable sorting algorithm?

Ned Horvath said...

Merge sort is stable, but isn't in-place -- you have to have double the space to merge from / into. In-place only allows compares and swaps. (I do know of a very elegant in-place stable sort that requires O(n times the square of (log n)). Suboptimal but still pretty fast, I can describe it if you care!

Javin Paul said...

Hello Ned, Yeah, sure, please go ahead. It would be useful for not only me but for my readers as well. Thanks a lot

Post a Comment