Sorting is the process of taking an initially unordered array of records and arranging them in some specific target order. The target order is specified by a comparison function which, given two records, decides which one should come first. For example, if the records are two integers, the comparison function may be the rule: "put the smaller number earlier in the list." There are many sorting algorithms, and some can be quite computationally complex. The main justification for going through the process of sorting is that once it is done it is relatively easy to find records in the sorted list using fast algorithms such as binary search.

An important criterion used to rate sorting algorithms is their running time. Running time is measured by the number of computational steps it takes the sorting algorithm to terminate when sorting n records. We say that an...