QuickSort

QuickSort picks a pivot element, partitions the array so smaller elements are left and larger elements are right, then recursively sorts each side.

The idea:

$1.$ Choose a pivot (often the last element).

$2.$ Partition: rearrange so elements $<$ pivot are left, elements $>$ pivot are right.

$3.$ Recursively sort left and right partitions.

Example for $[10, 80, 30, 90, 40, 50, 70]$ with pivot $70$:

After partition: $[10, 30, 40, 50, 70, 90, 80]$. Pivot $70$ is in its final position. Recursively sort $[10, 30, 40, 50]$ and $[90, 80]$.

Unlike merge sort, quicksort does work before recursing (partition) rather than after (merge).