**QUICK-SORT**

**Input**: Let be the list to be sorted.

**Algorithm**: Pick a pivot element ; let and . Recursively compute and . Output .

**Correctness**: By induction on the size of the list to be sorted. The base case is when in which case correctness is obvious. The inductive step follows by observing that .

**Running Time**: In the worst case quick sort takes , e.g., when the original list is already sorted and we take the pivot to be the first element at every step. This is because in the step we have while and so the total running time is . Observe that the running time can never exceed . This is because there are unique pair-wise comparisons that can be made on elements of and the only comparison made at any step is with the pivot element, hence no comparison is ever repeated (since the pivot is discarded in the subsequent recursive calls to ).

**Improving the choice of pivot**: If the two parts and are of equal size, then the total running time is . Let represent the time takes on a list of size . Then we get .

The idea is to pick a random pivot element : later in the course, we will see that with good probability the two partitions will be approximately balanced, leading to an overall running time of .

**MERGE-SORT**

**Input**: Let be the list to be sorted.

**Algorithm**: Partition the list into two equal size parts and let and be computed recursively. Then output , which merges these two sorted lists in linear time.

:

- If return
- Else if return
- Else if return
- Else return .

**Correctness**: By induction on the size of the list. The base case is when , in which case correctness is trivial. Since they are correctly sorted by the inductive hypothesis and correctly merges two sorted lists into a single sorted list.

**Running Time**: Note that takes time linear in . Thus if is the time it takes to merge-sort a list of numbers, then we get the following recurrence relation: , which implies .