Chapter 12
Sorting and Selection
Contents
12.1.2 Array-Based Implementation of Merge-Sort
12.1.3 The Running Time of Merge-Sort
12.1.4 Merge-Sort and Recurrence Equations 
12.1.5 Alternative Implementations of Merge-Sort
12.2.2 Additional Optimizations for Quick-Sort
12.3 Studying Sorting through an Algorithmic Lens
12.3.1 Lower Bound for Sorting
12.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort
12.4 Comparing Sorting Algorithms
12.5.2 Randomized Quick-Select
12.1 Merge-Sort
We have introduced several sorting algorithms thus far, including insertion-sort (see Sections 3.1.2, 7.6, and 9.4.1); selection-sort (see Section 9.4.1); bubble-sort (see Exercise C-7.51); and heap-sort (see Section 9.4.2). In this chapter, we will present four other sorting algorithms, called merge-sort, quick-sort, bucket-sort, and radix-sort, and then discuss the advantages and disadvantages of the various algorithms in Section 12.4.
12.1.1 Divide-and-Conquer
The first two algorithms we describe in this chapter, merge-sort and quick-sort, use recursion in an algorithmic design pattern called divide-and-conquer. We have already ...
Get Data Structures and Algorithms in Java, 6th Edition 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.
