Sorting --- Extensions, general issues, and questions

1. A stable sort is one in which records with the same key value are guaranteed to appear in the final list in the order in which they appeared in the original. Any sort can be made stable by adding the original position as an extra field to each record, and using this as a tiebreaker. The more interesting question is: which of the above sorts are stable, or can easily be made stable, without adding additional information to records.
2. Additional information about the distribution of keys, or about the current and correct positions of records in the original list, can affect which sorts behave reasonably. Which sorts (either from the above list, or designed for the special case) are effective in each of the following cases?

• There are at most some small number k of distinct keys.
• At most k records are out of correct relative order.
• Each record is at most k positions away from its correct position.
• If record1 is to the right of record2, then record1.key + k > record2.key.
• The list consists of k sorted clumps.
• Only the smallest k, or the largest k, values are needed.

1. A sorting technique is incrementalizable if it can

• accommodate addition of a new value in the middle of the process, and
• fix any errors if the key value of a record is changed in the middle of the sort.
• What are some characteristics of these techniques?
• Which of the techniques above are incrementalizable?

1. Movement of records is particularly expensive.

• Although selection sort has very bad time performance, it performs only O(n) swaps, while bubble sort or quicksort with a reverse-sorted list pretty demonstrably take O(n^2) swaps.
• Insertion sort will typically make O(n^2) swaps, heap sort will make O(n lg n), etc.
• A linked-list implementation of insertion sort does no movement, but at the cost of requiring pointers in records.