Divide and conquer Quicksort an n-element array 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray xs elements in upper subarray X X x 2. Conquer: Recursively sort the two subarrays 3. Combine: Trivial Key: Linear-time partitioning subroutine Day 6 Introduction to Algorithms L4.3Day 6 Introduction to Algorithms L4.3 Divide and conquer Quicksort an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray. 2. Conquer: Recursively sort the two subarrays. 3. Combine: Trivial. ≤≤xx xx ≥≥xx Key: Linear-time partitioning subroutine