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: Fundamentals, Data Structures, Sorting, Searching now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.