xvi Contents 3.6 Recurrence Equations 130 3.7 Recursion Trees 134 Exercises 141 Notes and References 146 4 Sorting 149 4.1 Introduction 150 4.2 Insertion Sort 151 4.3 Divide and Conquer 157 4.4 Quicksort 159 4.5 Merging Sorted Sequences 171 4.6 Mergesort 174 4.7 Lower Bounds for Sorting by Comparison of Keys 178 4.8 Heapsort 182 4.9 Comparison of Four Sorting Algorithms 197' 4.10 Shelisort 197 4.11 Radix Sorting 201 Exercises 206 Programs 221 Notes and References 221 5 Selection and Adversary Arguments 223 5.1 Introduction 224 5.2 Finding max and min 226 5.3 Finding the Second-Largest Key 229 5.4 The Selection Problem 233 5.5 A Lower Bound for Finding the Median 238 5.6 Designing Against an Adversary 240 Exercises 242 Notes and References 246 6 Dynamic Sets and Searching 249 6.1 Introduction 250 6.2 Array Doubling 250 6.3 Amortized Time Analysis 251 6.4 Red-Black Trees 253 6.5 Hashing 275 6.6 Dynamic Equivalence Relations and Union-Find Programs 283 6.7 Priority Queues with a Decrease Key Operation 295 Exercises 302