Stable Sorts

Another less obvious property we should worry about when sorting is the stability of the sort. Before we define what that means, consider the following example: Suppose we have an array of student records. Each record includes the student's last name, their first year of attendence, and other useful information (grades, contact information, etc.). Now suppose we wish to sort these to create alphabetical lists by last name for each year of attendence, in order. To do this, we first sort the records by last names. The below list gives a sample of how the records might now be organized. Note the order in which the 2019 students appeared (shown in yellow).

Last nameFirst yearPhone$\cdots$
Albert2018231-343-5555$\cdots$
Creed2019898-122-9643$\cdots$
Douglas2020874-088-1212$\cdots$
Elmer2019644-480-0023$\cdots$
Francis2019762-555-3987$\cdots$
Harris2020872-322-9768$\cdots$
King2019766-093-9873$\cdots$
Smith2018991-878-4944$\cdots$
Zhu2020991-675-1001$\cdots$

Now, we sort the above list by the first year of attendence to obtain:

Last nameFirst yearPhone$\cdots$
Albert2018231-343-5555$\cdots$
Smith2018991-878-4944$\cdots$
Creed2019898-122-9643$\cdots$
Elmer2019644-480-0023$\cdots$
Francis2019762-555-3987$\cdots$
King2019766-093-9873$\cdots$
Douglas2020874-088-1212$\cdots$
Harris2020872-322-9768$\cdots$
Zhu2020991-675-1001$\cdots$

Notice that the second sort in this case gave us exactly what we wanted -- students grouped by first year and alphabetized by last name. This worked out the way it did because the order of students with the same first year of attendence in our initial list was preserved when we sorted by first year of attendence. For example, in the first list, the 2019 students appear in the order "Creed, Elmer, Francis, King". After sorting by first year, this order was preserved. This motivates a definition -- when a sort preserves the relative order of elements of equal rank, we say that the sort is stable.

It could have gone another way though. What if the sorting by first year of attendence had produced the following?

Last nameFirst yearPhone$\cdots$
Smith2018991-878-4944$\cdots$
Albert2018231-343-5555$\cdots$
Francis2019762-555-3987$\cdots$
Creed2019898-122-9643$\cdots$
Elmer2019644-480-0023$\cdots$
King2019766-093-9873$\cdots$
Zhu2020991-675-1001$\cdots$
Douglas2020874-088-1212$\cdots$
Harris2020872-322-9768$\cdots$

This time, while the 2019 students were initially in the order "Creed, Elmer, Francis, King", now they are in the order "Francis, Creed, Elmer, King". In other words, the sorting by first year undid some of the work the sorting by last name had accomplished. When a sorting method can change the relative order of elements of equal rank, we say the sort is not stable.

Clearly, when one wants to follow one sort with another, without undoing the work of the first sort, one should consider using a stable sort over an unstable one.

Wondering now which of the sorts we have examined are stable? Let's take a look: