# Jan 9. Sorting

QUICK-SORT

Input: Let $A$ be the list to be sorted.

Algorithm: Pick a pivot element $p \in A$; let $A_1 = (a \mid a\in A, a \le p)$ and $A_2 = (a \mid a \in A, a > p)$. Recursively compute $B_1 = QUICKSORT(A_1)$ and $B_2 = QUICKSORT(A_2)$. Output $(B_1, p, B_2)$.

Correctness: By induction on the size of the list to be sorted. The base case is when $|A|=1$ in which case correctness is obvious. The inductive step follows by observing that $|B_1|, |B_2| < |A|$.

Running Time: In the worst case quick sort takes $\frac{n(n-1)}{2}$, 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 $i^{th}$ step we have $|A|=n-i+1$ while $|A_1|=0, |A_2|=n-i$ and so the total running time is $\sum_{i=1}^n n-i = \frac{n(n-1)}{2}$. Observe that the running time can never exceed $\frac{n(n-1)}{2}$. This is because there are $\frac{n(n-1)}{2}$ unique pair-wise comparisons that can be made on elements of $A$ 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 $QUICKSORT$).

Improving the choice of pivot: If the two parts $A_1$ and $A_2$ are of equal size, then the total running time is $O(n \log{n})$. Let $T(n)$ represent the time $QUICKSORT$ takes on a list of size $n$. Then we get $T(n) = 2 T(n/2) + O(n)$.

The idea is to pick a random pivot element $p$: 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 $O(n \log n)$.

MERGE-SORT

Input: Let $A$ be the list to be sorted.

Algorithm: Partition the list into two equal size parts $A_1, A_2$ and let $B_1 = MERGESORT(A_1)$ and $B_2 = MERGESORT(A_2)$ be computed recursively. Then output $MERGE(B_1,B_2)$, which merges these two sorted lists in linear time.

$MERGE(B_1, B_2)$:

• If $|B_1| = 0$ return $B_2$
• Else if $|B_2| = 0$  return $B_1$
• Else if $B_1[0] \le B_2[0]$ return $(B_1[0], MERGE(B_1 \setminus B_1[0], B_2))$
• Else return $(B_2[0], MERGE(B_1, B_2 \setminus B_2[0]))$.

Correctness: By induction on the size of the list. The base case is when $|A| = 1$, in which case correctness is trivial. Since $|B_1|, |B_2| < |A|$ they are correctly sorted by the inductive hypothesis and $MERGE$ correctly merges two sorted lists into a single sorted list.

Running Time: Note that $MERGE(B_1, B_2)$ takes time linear in $|B_1|+|B_2|$. Thus if $T(n)$ is the time it takes to merge-sort a list of $n$ numbers, then we get the following recurrence relation: $T(n) = 2T(\frac{n}{2}) + O(n)$, which implies $T(n) = O(n\log{n})$.