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 Nk 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 ...

Get Algorithms in Java, Third Edition, Parts 1-4 now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.