Mergesort

Split the list into 2 halves, recursively sort each half and then merge the two sorted sublists. For merging $x[1..k]$ and $y[1..l]$ into $z[1..k+l]$. The first element of $z$ is smaller of $x[1]$ and $y[1]$ and rest can be constrcuted recrusively.

\[\begin{align} \text{mergesort}(a[1..n]) =&\text{merge}(\text{mergesort}(a[1..\lfloor n/2\rfloor]),\\&\quad\text{mergesort}(a[\lfloor n/2\rfloor+1...n]))\\ \text{merge}(x[1..k],y[1..l])=&\begin{cases}x[1]\circ\text{merge}(x[2..k],y[1..l])&x[1]\le y[1]\\y[1]\circ\text{merge}(x[1..k],y[2..l])&\text{otherwise}\end{cases} \end{align}\]

Time Complexity $T(n)=2T(n/2)+O(n)\implies O(n\log n)$

Quicksort & Quickselect

Select a pivot $v$ (pick randomly). Split the array into three categories: elements smaller than $v$, those equal to $v$ and those greater than $v$. Call these $S_L$, $S_v$, and $S_R$ respectively. Recursively sort the array.

Time complexity: $O(n^2)$ worst case. $O(n\log n)$ best and average case.

For selecting the $k^{\rm th}$ element: \(\text{selection}= \begin{cases} \text{selection(S_L, k)}&k\le |S_L|\\ v &|S_L|<k\le|S_L|+|S_v|\\ \text{selection}(S_R, k-|S_L|-|S_v|)&k>|S_L|+|S_v| \end{cases}\) Time complexity: $T(n)=T(n/2)+O(n)\implies O(n)$