stable sort

Stable sort is a category of sorting algorithms that do not change the relative order of two or more equivalent elements. But question is how does it matter?

e.g. if I have few  elements in a list : 5,4,6,4,9,8,10

Let us call first 4 as 4/1 and second one as 4/2.

5/1, 4/1, 6, 4/2, 9, 8, 10

And after sorting result could be one of the following :

4/1,4/2,5,6,8,9,10

or

4/2,4/1,5,6,8,9,10

Is there any difference in two results? No there is no difference, To the user both 4 are same and equal.

Difference would arise if I have to sort user defined datatype say students.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class student { int roll_num; char *name; char *address; public : //! constructor //! destructor //! copy constructor student(const student &rhs) { roll_num = rhs.roll_num; name = new char[strlen(rhs.name)+1]; strcpy(name,rhs.name); address = new char[strlen(rhs.address)+1]; strcpy(address,rhs.address); } }; int main() { student st[5] = { {1,"abcdef","address1"}, {2,"zyxw","adress2"}, {3,"wert","address2"}, {4,"abcdef","address3"}, {5,"qwerty","address4"} }; }

Here array st contains information of 5 students and if you notice it is automatically sorted by their roll number but now say you want to sort them with their name. What should be the order after sorting?

st[0], st[3], st[4], st[2], st[1] 

OR

st[3], st[0], st[4], st[2], st[1] 

Unlike case of integers, both are not equal. st[3] and st[0] are equivalent in their name only. So a sorting algorithm which is stable will place st[0] before st[3]. It will not change their relative order.

We have different sorting algorithms like merge sort, quick sort, insertion sort, bubble sort etc etc. Which one of them is stable and which is not? Generally people use merge and quick sort because of their complexity of order (nlogn).

Merge sort is stable while quick sort is not (reason/explanation behind this is out of scope of this post).
So this can be one factor in choosing sorting algorithm. If your application requires stable sorting, you can't simply rely on quicksort.


Could you think of an application that use stable sort?

 There are many. One of them that came to my mind is that when we try to sort different items in Microsoft windows Explorer based on different parameters.

FIGURE1 : Items sorted on name

FIGURE2 : Items sorted on date modified 

In the Figure 1, you can see that items are sorted on their name field.
In the Figure 2, items are sorted based on their last modified date.

In Figure 2, DRIVERS and vpn folders have same time stamp but DRIVERS is kept ahead of vpn so that their relative order is not changed


Did you know that Java internally uses quicksort for sorting built-in data types like int, double etc as we saw that for built-in types relative order does not matter but for user-defined data types, it uses merge sort so that relative order is not changed.