In many cases it is necessary to take a sequence of values and sort them in some specified order. For example, a list of class examination scores may be sorted by decreasing order of scores, or by the identification number of the students in the class. In most cases, there is a record with several fields, such as student's name, number, score, and grade. A field such as the score which is sorted against is called a key, while other fields are considered ancillary to it and are referred to as satellite data. When a sorting algorithm rearranges the order of the key fields, it rearranges the satellite fields as well. However, these details are often irrelevant in considering the question of the methods to be used for sorting, as details of implementation are usually left to the programmer. For purposes of understanding the algorithms, we pretend that...