Sort stability : Stable vs unstable sort

Recently stumbled upon this basic sorting concept of sort stability and it reminded me how in my college days we learnt about this but never appreciated the importance of this concept.

Definition as per Wikipedia.

Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

Let’s take an example. We will sort a collection of employees first with an unstable sort ( e.g. Quicksort) and then with a stable sort (e.g. merge sort) and then see the difference.

public class Employee
{
public string Name { get; set; }
public int Age { get; set; }
public string Designation { get; set; }
public string Paygrade { get; set; }
public string Department { get; set; }

public override string ToString()
{
StringBuilder sb = new StringBuilder();

sb.AppendLine("------------------------------------------------------------------");
sb.AppendLine($"Name : {this.Name}");
sb.AppendLine($"Department : {this.Department}");
return sb.ToString();
}

}

We will sort employees first with Name and then with the department. Below is the input.

We see that data is unsorted. We will focus on employees in department product management as we multiple people in this department.

Sorting with an unstable sort

Sort with employee name

Now the whole list is sorted according to name.

Sort with department name

Now if you see the moment we sorted by department name the sorting by name is disturbed and within the department ‘Project management’ names are no more sorted.

Now you can imagine in many applications in day to day life where this is an undesirable result.

This is where stable sorts come into the picture.

Sorting with a stable sort

Considering the same input list as above.

Sort with employee name

For obvious reasons, sorting with the name would be exactly same as above.

Sort with department name

In the above output if you notice that within Project management the employees are still sorted with  Name i.e. the relative ordering of the input is still maintained.

This is exactly what a stable sort provides you.

You can access the code here and play around by plugging different sorting algorithms and see how they behave. I used quicksort for unstable sort and merge sort for stable sort algorithm in this example.

Concluding remarks

Now looking at this you must be able to realize many applications which you might be using where this concept applies e.g. your song list in Spotify….try sorting it by name and then by album or artist. It is stable. But the story does not fully end here. There are ways in which you can make an unstable algorithm stable and vice-versa.E.g below is a snapshot of merge sort algorithm I wrote and just by changing the one condition below we will change this stable algorithm to an unstable one. Mind you the algorithm would still work perfectly well with the same performance and time complexity.

Obvious questions I had in my mind while writing this post was to see what kind of algorithm (i.e. stable vs unstable) does .NET uses for sorting arrays and collections but I did not find a definitive answer (discussion here & here). Using my example I tried two of them i.e. Array.Sort and LINQ order by and both of them seem to behave stably. Try and out and comment if you find a definite answer.

Furthermore, if you are interested in learning more on algorithms and data structure you can follow this course on pluralsight (I am going through it right now) and it seems to be good. It goes without saying that you will need to refer other material for learning this like books and other online resources e.g. geeksforgeeks.org  etc..