# 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)$$.
### 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.
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook/32.-more-quick-sort-sorting-summary/32.2-quick-select.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.