Data Structures and Algorithms in Python

Chapter 12

Sorting and Selection

Contents

12.1 Why Study Sorting Algorithms?

12.2 Merge-Sort

12.2.1 Divide-and-Conquer

12.2.2 Array-Based Implementation of Merge-Sort

12.2.3 The Running Time of Merge-Sort

12.2.4 Merge-Sort and Recurrence Equations

12.2.5 Alternative Implementations of Merge-Sort

12.3 Quick-Sort

12.3.1 Randomized Quick-Sort

12.3.2 Additional Optimizations for Quick-Sort

12.4 Studying Sorting through an Algorithmic Lens

12.4.1 Lower Bound for Sorting

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

12.5 Comparing Sorting Algorithms

12.6 Python's Built-In Sorting Functions

12.6.1 Sorting According to a Key Function

12.7 Selection

12.7.1 Prune-and-Search

12.7.2 Randomized Quick-Select

12.7.3 Analyzing Randomized Quick-Select

12.8 Exercises

12.1 Why Study Sorting Algorithms?

Much of this chapter focuses on algorithms for sorting a collection of objects. Given a collection, the goal is to rearrange the elements so that they are ordered from smallest to largest (or to produce a new copy of the sequence with such an order). As we did when studying priority queues (see Section 9.4), we assume that such a consistent order exists. In Python, the natural order of objects is typically¹ defined using the < operator having following properties:

• Irreflexive property: ...