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. ≤x x≤ 2. Conquer: recursively sort the two subarrays 3. Combine: Trivial Key: Linear-time partitioning subroutineDivide 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. ≤ x x x ≤ 2. Conquer: Recursively sort the two subarrays. 3. Combine: Trivial. Key: Linear-time partitioning subroutine