6.9 Bucket Sort
Distribute elements into buckets by value range, sort each bucket, then concatenate — achieving linear expected time on uniformly distributed input.
Tag
Linear-Time
3 notes
3 notes
Distribute elements into buckets by value range, sort each bucket, then concatenate — achieving linear expected time on uniformly distributed input.
Sort keys digit by digit using a stable subroutine, achieving linear time for fixed-width integers without any key comparisons.
Sort integer keys from a small range in linear time by counting occurrences and reconstructing the output from those counts.