Bucket Sort

By the end, you can

• Explain why bucket sort can beat the O(n log n) lower bound that applies to comparison-based sorts (it distributes elements by value instead of comparing them).
• Compute the bucket index for any value using the formula floor(n · value) for inputs in [0, 1), or the scaled form floor(n · (value − min) / (max − min + 1)) for an arbitrary range.
• Trace all three phases — scatter, sort, gather — on a small input.
• Explain why the gather phase requires no merge step.
• Describe the expected O(n) analysis in terms of E[n_i²] and state the assumption it relies on (inputs are spread uniformly across the buckets).
• Identify the worst-case scenario (all values clustered into one bucket), state its cost (it degrades to the inner sort's complexity, O(n²) or O(n log n)), and explain why.
• Name the key trade-offs: extra O(n + k) space for the buckets and the reliance on a uniform input distribution for its speed advantage.
• Place bucket sort in its algorithm family alongside counting sort and radix sort as a non-comparison, distribution-based sort.