Distribution sort: scatter elements into k buckets, sort each bucket independently, then gather buckets in order. O(n) average on uniform input; O(n^2) worst on skewed input.
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| Scatter | O(n) | O(n) | O(n) | One pass |
| Inner sort (per bucket) | O(1) | O(1) | O(n^2) | Insertion sort |
| Gather | O(n + k) | O(n + k) | O(n + k) | Concatenation |
| Total time | O(n + k) | O(n) | O(n^2) | O(n) when k ≈ n, uniform |
| Space | O(n + k) | O(n + k) | O(n + k) | Not in-place |