如何确定桶排序（Bucket Sort）的平均及最坏情况空间复杂度？

Alright, let’s break this down step by step—no overly formal jargon, just straight-up reasoning tied to how bucket sort actually works. First, a quick recap of the algorithm’s core flow, since we can’t talk complexity without knowing what we’re measuring:

1. Split the input value range into k buckets (e.g., splitting [0,1) into k equal subintervals).
2. Iterate through all n input elements and drop each one into its corresponding bucket.
3. Sort each non-empty bucket individually (common choices: insertion sort, quicksort, or recursive bucket sort).
4. Concatenate all sorted buckets to get the final ordered array.

Space complexity accounts for three key parts: the space used to hold the bucket structure, the space to store all input elements, and any auxiliary space needed for sorting individual buckets.

Average Case Space Complexity #

Bucket sort shines when input elements are uniformly distributed. In this scenario, we almost always choose k = n (one bucket per element on average)—this minimizes the number of elements per bucket and speeds up sorting. Let’s crunch the numbers:

• Bucket structure space: We create n buckets, so this takes O(n) space (think of an array holding references to each bucket, even empty ones).
• Element storage space: With uniform distribution, each bucket holds ~n/k = 1 element on average. Total elements are still n, so this is O(n) space.
• Auxiliary sorting space: On average, buckets have so few elements that we either don’t need to sort them at all, or use an in-place algorithm like insertion sort (which uses O(1) auxiliary space).

Adding these up: O(n) + O(n) + O(1) = O(n). That’s our average case space complexity.

Worst Case Space Complexity #

The worst case hits when all elements land in a single bucket (e.g., every input element is identical, or the distribution is extremely skewed). Let’s break this down:

• Bucket structure space: Even if n-1 buckets are empty, if we chose k = n, this still takes O(n) space (the bucket array itself doesn’t shrink just because buckets are empty).
• Element storage space: All n elements are in one bucket, but we’re still storing the same total number of elements—so this remains O(n).
• Auxiliary sorting space: Now we have to sort n elements in one bucket. If we use an in-place algorithm (insertion sort, bubble sort), this is O(1). If we use recursive quicksort, worst-case auxiliary space is O(log n) (from the recursion stack). Even if we use mergesort (which needs O(n) auxiliary space for the bucket’s elements), this adds O(n) to the total.

Adding these up: O(n) + O(n) + O(n) = O(n). Even in the worst case, the space complexity stays linear—no exponential blowup here.

A quick side note: If you chose a tiny k (like k=1, which is just using the bucket’s sorting algorithm directly), the bucket structure space becomes O(1), but the total space still lands at O(n) because of element storage and auxiliary sorting space.

内容的提问来源于stack exchange，提问作者Armaan