Counting/Radix Sort

Comparison-based sorting algorithms like Merge Sort and Quicksort have a theoretical lower bound of Ω(n log n). However, non-comparison sorts can achieve better performance by making assumptions about the input data. Counting Sort is one such algorithm that runs in O(n + k) time, where `n` is the number of elements and `k` is the range of the input values. It works by creating a 'count' array to store the frequency of each distinct element in the input array. Then, a second pass is made to modify the count array to store the cumulative counts, effectively determining the position of each element in the sorted output. Finally, the input array is traversed backwards, and elements are placed into the output array at their correct positions. It's extremely efficient but only practical when the range `k` is not significantly larger than `n`. Radix Sort builds upon this idea to sort elements with a larger range. It sorts the input numbers digit by digit (or byte by byte), starting from the least significant digit to the most significant. For each digit, it uses a stable sorting algorithm (like Counting Sort) to sort the numbers based on that digit. The stability is crucial, as it ensures that the ordering from previous digit sorts is not disturbed. For `d` digits in numbers up to `k`, Radix Sort has a complexity of O(d * (n + k)), which can be linear if `d` is constant.