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

No credit card required

# Chapter 11. 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.

No credit card required