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 likeData 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 likeAlgorithms and Data Structures - Part 1 and 2 on Pluarlsight. It is one of the comprehensive course in algorithms for Java programmers.

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:

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

5 Books to Learn Data Structure and Algorithms

20 String Algorithm Interview Questions

20 Array-based Interview Questions

15 Data Structure and Algorithm Interview Questions

Introduction to Algorithms by Thomas H. Cormen

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.