• all comparison-based sorting algorithms are bound by $\Omega(n\ log(n))$
  • Proof
• thus, in order to achieve a linear runtime $\Theta(n)$, we must manufacture an alternative way of sorting our data

Counting Sort — count occurrences of each element

Bucket Sort — recursively places items into buckets

Radix Sort — sorts by processing individual digits

Counting Sort

Bucket Sort

Radix Sort