tag

#linear-time

3 pages tagged

Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.9 Bucket Sort

6.9 Bucket Sort Bucket sort distributes elements into groups, sorts each group, and then concatenates the results. It relies on an assumption about the input distribution. When elements are spread roughly uniformly over a known range, bucket sort can run in linear time. Problem You have an array A[0..n-1] of real numbers in a known interval, typically [0, 1) . You want a sorting algorithm that exploits this range and...
algorithms sorting bucket-sort linear-time May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.7 Counting Sort

6.7 Counting Sort Counting sort replaces comparisons with counting. It assumes keys come from a small integer range and uses that structure to achieve linear time. Instead of ordering elements directly, it counts how many times each key appears and reconstructs the sorted output from those counts. Problem You have an array A[0..n-1] where each element is an integer in a known range [0, k] . You want a stable...
algorithms sorting counting-sort linear-time May 4, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.8 Radix Sort

6.8 Radix Sort Radix sort sorts keys one digit at a time. It avoids direct comparisons between full keys by repeatedly applying a stable sort to smaller key components. For integers, those components are usually digits in base 10 , base 256 , or another fixed radix. Problem You have an array of nonnegative integers. You want to sort them in linear time relative to the number of elements and...
algorithms sorting radix-sort linear-time May 4, 2026