Linear-Time Sorting Algorithms (Non-Comparison Based)

Key Insight

Beyond comparison sorts, there exist algorithms that achieve linear time complexity by leveraging specific assumptions about the input data, thus circumventing the Omega(n log n) lower bound. Counting sort is one such algorithm, assuming that the 'n' input elements are integers within a limited range, specifically from 0 to 'k'. It operates by determining the count of elements less than each input value, allowing direct placement into the output array. It achieves Theta(k+n) time, making it linear if 'k' is proportional to 'n'. Notably, counting sort does not use comparisons between input elements but rather uses element values as array indices, and it is a stable sort.

Radix sort extends the capabilities of counting sort to handle multi-digit numbers or keys with multiple fields. It processes numbers digit by digit, from the least significant digit to the most significant. For each digit position, it employs a stable sorting algorithm, such as counting sort, to sort the entire list based on that digit. With 'd' digits and each digit taking on 'k' possible values, radix sort runs in Theta(d(n+k)) time. For 'n' b-bit numbers, by viewing keys as 'd = ceil(b/r)' digits of 'r' bits each, it runs in Theta((b/r)(n + 2^r)) time, achieving linear time if 'd' is constant and 'k = O(n)', or if 'b' is 'O(log n)' and 'r' is chosen as 'log n'.

Bucket sort is another linear-time algorithm that assumes input numbers are drawn from a uniform distribution over a specific interval, commonly [0, 1). It divides this interval into 'n' equal-sized 'buckets', distributes the input numbers into these buckets, then sorts the elements within each bucket (often using insertion sort), and finally concatenates the sorted buckets. While its worst-case running time is Theta(n^2) (if all elements fall into a single bucket), its average-case running time is O(n). This efficiency stems from the uniform distribution assumption, which ensures that on average, few elements are placed in each bucket, making the bucket-sorting step quick.