Indian Computing Olympiad

Sorting

Stable sorting

An additional property that is desirable in a sorting algorithm is stability. This says that two values that are equal in the original array are never swapped in the process of sorting.

This is important if we sort data multiple times on different criteria. Suppose we have an array in which values are pair of the form (name, marks). We want the final output to have the arrays arranged in ascending order of marks. Since there may be multiple students with the same marks, we want to sort the students with the same marks by alphabetical order of name.

If we have a stable sorting algorithm, we can do this as follows:

1. First sort the whole array by name
2. Then sort the whole array by marks

The second sort does not disturb the order of students with equal marks, so all students with equal marks retain their alphabetical order.

Mergesort is a stable sort (we ensured this by saying that we pick the element from the left when merging if the two values being compared are equal.) Quicksort, as described in these notes, is not stable. (Why?)