Question: Exercise addressed stable sorting. Write a method that performs a stable quicksort. To do so, create an array of objects; each object is to contain a data item and its initial position in the array. (This is the Composite pattern; see Section 3.9.) Then sort the array; if two objects have identical data items, use the initial position to break the tie. After the array of objects has been sorted, rearrange the original array.
Exercise: A sorting algorithm is stable if elements with equal keys are left in the same order as they occur in the input. Which of the sorting algorithms in this chapter are stable and which are not? Why?