# 32.2 Quick Select Dissatisfied with the result that Quicksort is unable to completely defeat Mergesort and truly claim the title for "fastest comparison-based sorting" algorithm, let's shoot our one last shot to overturn the result: use Quick Select to identify the median. ## Quick Select Algorithm Goal: find the median using partioning. Key idea: Median of an length n array will be around index n /2. 1. Initialize array with the leftmost item as the pivot.

Initial Array

For this example, the index of the median should be 9 / 2 = 4. 2. Partition around pivot.

Pivot lands at index 2

Since the pivot is at index 2, which is not the median. Therefore, need to continue. However, will only partition the **right** subproblem because median can't be to the left! (index n/2 > 2) 3. Partition the subproblem. Repeat the process.
Pivot is at index 6, which means that it is not at the median. Continue. 4. Stop when the pivot is at the median index.
Since pivot is at index 4, we are done. ## Quick Select Performance ### Worst Case Runtime The worst case is when the array is in sorted order, which yields a runtime of $$\theta(N^2)$$. ![](https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2FYMATfSuOMSDvBWsFU8LR%2FScreen%20Shot%202023-04-10%20at%2012.47.27%20AM.png?alt=media\&token=f2e3f0af-3b98-4395-aacc-e1f33b19fd32) ### Expected Runtime The expected runtime for the Quick Select Algorithm is $$\theta(N)$$. Here's an intuitive diagram that justifies this result:
Using one of our favorite sums, we can see the runtime is: $$ N + N/2 + N/4 +.... + 1 = \theta(N) $$ ## Compared to MergeSort? Unfortunately, even using Quickselect to find the exact median, the resulting algorithm is still quite slow. Team Mergesort wins, sadly.