Kth Largest Element - QuickSelect

QuickSelect is a selection algorithm based on QuickSort's partition. Instead of sorting both halves, you only recurse into the half containing the $k$th element.

$1.$ Pick a pivot and partition the array.

$2.$ If the pivot lands at position $k-1$, you found the answer.

$3.$ If pivot position $> k-1$, recurse left.

$4.$ If pivot position $< k-1$, recurse right.

Average case is $O(n)$ because you halve the problem each time: $n + n/2 + n/4 + ... = 2n$.