O'Reilly logo

Algorithms Third Edition in C++ by Robert Sedgewick

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter EightMerging 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required