Distributes elements into N buckets by value range, sorts each bucket with insertion sort, then concatenates. Performance depends heavily on data distribution.
Step 1: Create N empty buckets for value ranges. Step 2: Distribute each element into its corresponding bucket. Step 3: Sort each bucket individually (insertion sort). Step 4: Concatenate all buckets in order.
With uniform data, each bucket gets ~n/k elements, giving O(n+k) average. With clustered data, one bucket gets most elements, degrading to O(n^2).