Difference between Stable and Unstable Sorting Algorithm - MergeSort vs QuickSort

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 the 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 the quicksort is unstable but merge sort is a stable sorting algorithm.  Btw, If you are not familiar with essential sorting algorithms like Quicksort and Mergesort then I suggest you join a comprehensive data structure course like Data Structures and Algorithms: Deep Dive Using Java.  It will provide you with all the fundamental knowledge you need to explore further.

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 the 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 take some good course on Data Structure and Algorithms like Algorithms and Data Structures - Part 1 and 2 on Pluarlsight. It is one of the comprehensive course in algorithms for Java programmers.

Difference between Stable and Unstable Sorting Algorithm?

Btw, you would need a Pluralsight membership to access this course, which costs around $29 monthly or $299 annually. I have one and I also suggest all developers have that plan because Pluralsight is like NetFlix for Software developers.

It has more than 5000+ good quality courses on all latest topics. Since we programmers have to learn new things every day, an investment of $299 USD is not bad.

Btw, it also offers a 10-day free trial without any obligation which allows you to watch 200 hours of content. You can watch this course for free by signing for that trial.

Stable vs Unstable Algorithm Example

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
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz

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. 

P. S. - Are you ready for Interview? Take TripleByte's quiz and go directly to the final round of interviews with top tech companies like Coursera, Adobe, Dropbox, Grammarly, Uber, Quora, Evernote, Twitch, and many more.


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

Marc Forward said...

re: ❛❛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!❜❜
i would be very grateful to see this.
thanks in advance,
〜Marc F.

Post a Comment