Comparison Lower Bound: Any comparison-based sorting algorithm has a theoretical lower bound of $\Omega(n \log n)$ worst-case comparisons, derived from decision tree heights $\log_2(n!) \approx n\log_2 n - 1.44n$.
Divide-and-Conquer ($\mathcal{O}(n\log n)$): Merge Sort divides arrays into halves and merges sorted sub-arrays in linear time. Quick Sort partitions around a pivot so elements left $\le$ pivot $\le$ elements right.
Heap Sort: Constructs a max-heap ($\mathcal{O}(n)$) and repeatedly swaps the root maximum to the tail ($\mathcal{O}(n\log n)$), achieving in-place $\mathcal{O}(1)$ auxiliary space.
Radix Sort ($\mathcal{O}(d \cdot (n + k))$): Non-comparison integer sort that processes individual digit places (LSD) using stable counting sort sub-routines.
Color Key: Default | Comparing | Swapping/Writing | Pivot | Sorted