Table of contents
When we have to sort an array or list on multiple criteria the concept of Stable Sorting is important. The Concept of whether the sorting is stable or unstable comes into the picture when we have to handle two same entries.
We will try to understand the same by taking an example. Assume we have listed students in alphabetical order. Now we want to sort students based on marks.
Name: A B C D E
Marks: 80 50 40 80 40
Now we can see that the given list is sorted in alphabetical order.
Now we have been given the task to sort the given array of elements based on marks.
Stable Sorting
When we will sort the array on a different condition (is this case based on marks ). We will maintain the previous order in the case on the same entries C and E have the same marks so taking the previous order C must be before E when sorting based on marks A and D have the same marks so taking the previous order A must be before D when sorting based on marks
Unstable Sorting
When we will sort the array on a different condition (is this case based on marks ). We will not maintain the previous order in the case of the same entries We do not guarantee where the previous order will be maintained or not
Example 1.
Stable Sorting
In Example 1
C is before E
A is before D Students with the same marks have to be in alphabetic order which means the alphabetic order is maintained.
So Sorting is said to be stable when sorting elements on a new condition does not disturb the previous sorted order of the elements. Merge Sort is an example of stable sorting
Unstable Sorting
In Example 1
E is before C
D is before A
The alphabetic order gets lost.
So Sorting is said to be unstable when sorting elements on a new condition does disturb the previous sorted order of the elements.
Quick Sort is an example of unstable sorting