Linear-Time Sorting: Counting, Radix, and Bucket Sort

Every sorting algorithm covered so far — insertion sort, mergesort, heapsort, quicksort — decides the relative order of elements purely by comparing them, and it turns out no such algorithm can beat $\Theta(n\log n)$ in the worst case, a fact this note proves first. But that lower bound has an escape hatch: if the keys being sorted have extra exploitable structure (bounded integer range, fixed-width digits, a known distribution), an algorithm that never compares two elements directly can sort in $\Theta(n)$. This note proves the comparison lower bound, then builds the three classical linear-time sorts — counting sort, radix sort, and bucket sort — each exploiting a different kind of structure.