Difference between stable and unstable sorting ?

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.

sort.png

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

Did you find this article valuable?

Support Vinayak tech Blog by becoming a sponsor. Any amount is appreciated!