Sorting is a fundamental operation in computer science. A good deal of effort in computing is related to making data available to users in some particular order. The concept of an ordered set of data is one that has considerable impact on our daily lives. For example, lists of names are frequently printed in alphabetical order and mailing labels are often printed in pin-code order. Sorting refers to arranging data in some given order, such as increasing or decreasing, with numeric data or alphabetically, with character data.
In this chapter we are concerned with rearranging the data so that it is in sorted order. There are two important and largely disjoint categories related to sorting data—internal sorting and ...