Difference between Stable and Unstable Sorting Algorithm - MergeSort vs QuickSort

Recently in one interview, after some initial questions about sorting algorithms e.g. how do you write QuickSort or the difference between QuickSort and MergeSort, the interviewer asked about do you understand the difference between stable and unstable sorting algorithms? This question was new to my reader, so he says, Sorry, never heard about that. The story ended there, and Interviewer moved on to the next question but like many of us, my reader went on to find more 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 the order of those first two ones then 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 the key-value pair is retained as shown in the following example.

Actually, the 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 differences 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 solutions 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 a stable sorting algorithm because the original order of equal keys is 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 the 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 unstable sorting algorithms.


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

If you are interested in learning more about this topic, I suggest you take some good courses on Data Structure and Algorithms like Algorithms and Data Structures - Part 1 and 2 on Pluralsight. It is one of the comprehensive courses in algorithms for Java programmers.

Stable vs Unstable Algorithm Example

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

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

Further Reading

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

Other coding Interview Questions for practice:

• TOp 30 linked list coding problems from Interviews (questions)
• How to remove duplicates from an array in Java? [solution]
• 10 Free Data Structure and Algorithms Courses (courses)
• Write a program to find the missing number in an integer array of 1 to 100? [solution]
• How do you reverse an array in place in Java? [solution]
• 50+ Data Structure and Algorithms Coding Problems from Interviews (questions)
• 10 Algorithms Books Every Programmer should read [books]
• 30+ Array-based Coding Problems from Interviews (questions)
• How to check if an array contains a number in Java? [solution]
• Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms courses to Crack Coding Interviews [courses]

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

P. S. - If you want to learn more about data structure and algorithms and looking for free data structure courses online then you can also check out this list of best free data structure and algorithms courses for Java and C programmer. This contains free algorithms courses from Udemy and Pluralsight for Java developers.