Problem

1. Suppose we have a very large list stored in external memory that needs to be sorted. Assuming that this list is too large for internal memory, what major factor(s) should be considered in designing an external sorting algorithm?

2. Classify the sorting algorithms discussed in this chapter based on the ideas behind the algorithms. For example, Heap sort and Selection Sort find the largest (or smallest) key and exchange it with the last (or first) element according to the desired order.

3. A stable sorting algorithm is one that preserves the original order of equal keys. Which of the sorting algorithms discussed in this chapter are stable? Which are unstable? Justify your answer.