Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, Third Edition

Chapter Eight. Merging and Mergesort

The quicksort family of algorithms that we studied in Chapter 7 are based on the selection operation: finding the kth smallest element in a file. We saw that performing selection is akin to dividing a file into two parts, the k smallest elements and the N – k largest elements. In this chapter, we examine a family of sorting algorithms based on a complementary process, merging: combining two ordered files to make one larger ordered file. Merging is the basis for a straightforward divide-and-conquer (see Section 5.2) sorting algorithm, and for a bottom-up counterpart, both of which are easy to implement.

Selection and merging are complementary operations in the sense that selection splits a file into two independent ...