Programming Pearls, 2nd Edition

Column 11: Sorting

How should you sort a sequence of records into order? The answer is usually easy: Use a library sort function. We took this approach in Solution 1.1 and twice in the anagram program in Section 2.8. Unfortunately, this plan doesn’t always work. Existing sorts may be cumbersome to employ or too slow to solve a particular problem (as we saw in Section 1.1). In such cases, a programmer has no choice but to write a sort function.

11.1 Insertion Sort

Insertion Sort is the method most card players use to sort their cards. They keep the cards dealt so far in sorted order, and as each new card arrives they insert it into its proper relative position. To sort the array x[n] into increasing order, start with the first element as the ...