O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

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 11. Sorting, Sets, and Selection

Sorting, Sets, and Selection

Contents

11.1 Merge-Sort

500

11.1.1 Divide-and-Conquer

500

11.1.2 Merging Arrays and Lists

505

11.1.3 The Running Time of Merge-Sort

508

11.1.4 C++ Implementations of Merge-Sort

509

11.1.5 Merge-Sort and Recurrence Equations *

511

11.2 Quick-Sort

513

11.2.1 Randomized Quick-Sort

521

11.2.2 C++ Implementations and Optimizations

523

11.3 Studying Sorting through an Algorithmic Lens

526

11.3.1 A Lower Bound for Sorting

526

11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort

528

11.3.3 Comparing Sorting Algorithms

531

11.4 Sets and Union/Find Structures

533

11.4.1 The Set ADT

533

11.4.2 Mergable Sets and the Template Method Pattern

534

11.4.3 Partitions with Union-Find Operations

538

11.5 Selection

542

11.5.1 Prune-and-Search

542

11.5.2 Randomized Quick-Select

543

11.5.3 Analyzing Randomized Quick-Select

544

11.6 Exercises

545

Merge-Sort

In this section, we present a sorting technique, called merge-sort, which can be described in a simple and compact way using recursion.

Divide-and-Conquer

Merge-sort is based on an algorithmic design pattern called divide-and-conquer. The divide-and-conquer pattern consists of the following three steps:

  1. Divide: If the input size is smaller than a certain threshold (say, one or two elements), solve the problem directly using a straightforward method and return the solution obtained. Otherwise, divide the input data into two or more disjoint subsets.

  2. Recur:

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