Linear Time Sorting Algorithms
Why O(n) is Possible
Comparison sorts need Omega(n log n) (decision tree with n! leaves). Linear sorts bypass this by not comparing elements — they use direct addressing, digit decomposition, or distribution.
Trade-off: O(n) time but requires assumptions about input (integers, bounded range, etc.) and extra space.
Counting Sort — O(n + k)
k = range of values. Stable. Used as subroutine in radix sort.
def counting_sort(arr, max_val=None):
[Description truncada. Veja o README completo no GitHub.]