An important property of sorting algorithms is stability. A sorting algorithm is stable if it preserves the original order of duplicate keys. Stability is important when sorting a collection that has already been sorted by a primary key that will now be sorted by a secondary key. For example, suppose we have a sequence of student records that have been sorted by name and now we want to sort the sequence by GPA. Since there can be many duplicate GPAs, we want to order any duplicates by name. Thus, if Smith and Green both have the same GPA, then Green would be listed before Smith. If the sorting algorithm used for this second sort is stable, then the proper ordering can be achieved since Green would appear before Smith in the original sequence.

(a) Determine which of the comparison sorts presented in this chapter and in Chapter 5 are stable sorts.

(b) For any of the algorithms that are not stable, provide a sequence containing some duplicate keys that shows the order of the duplicates is not preserved.