# Bucket sort for gaussian / standard distribution

I know this post. But I still have no idea to adapt the bucket sort algorithm to handle input with a gaussian / normal distribution. Can someone provide me a Pseudocode / Python code for that? So far I tried the following, but sadly it does not work, and I don't understand why.

def bucket_sort(numbers):
mean = sum(numbers) / len(numbers)
variance = sum((x - mean) ** 2 for x in numbers) / len(numbers)
std_deviation = math.sqrt(variance)

num_buckets = int( math.sqrt(len(numbers)) )
buckets = [[] for _ in range(num_buckets)]

for num in numbers:
index = int( ( (num - mean) / std_deviation) * num_buckets)
buckets[index].append(num)

for bucket in buckets:
bucket.sort()

sorted_numbers = [num for bucket in buckets for num in bucket]

return sorted_numbers


Let $$F$$ denote the cumulative distribution function for your distribution. Suppose you want $$N$$ buckets. Then use the following buckets:

$$(F^{-1}(0),F^{-1}(1/N)],(F^{-1}(1/N),F^{-1}(2/N)],\dots,(F^{-1}((N-1)/N),F^{-1}(1)].$$

This ensures that about $$1/N$$ of the samples fall into each bucket. Then, use bucket sort with these buckets.

To compute which bucket a value $$x$$ falls into, it suffices to compute the cdf for $$x$$. In particular, $$x$$ goes into bin number $$\lfloor F(x) N \rfloor$$.

This works for any distribution, assuming the distribution is known and you can compute the cdf.

• I really try to understand that, but I don't. First I have no idea how to compute/approximate that. Second: If I only compute the boundaries of the buckets, and not the indices, I have to loop over the element to find the correct bucket. I could improve this using binary search, but I still mess up the time complexity of bucket sort... Can you help me further, maybe provide a codeline for calculating the index, assuming the buckets have an index 0,1,...,b? May 23, 2023 at 17:30
• The inverse $\text{cdf}$ gives the bounds of the intervals. But to get the bucket where a given value goes, you need the direct $\text{cdf}$.
– user16034
May 24, 2023 at 6:40
• @YvesDaoust, oh, right! Thank you. Answer edited accordingly.
– D.W.
May 24, 2023 at 15:42

So I finally understand, what is happening. The input is distributed with a normal distribution. This leads us to a normal probability distribution function PDF for the probability of the elements. We can describe the distribution using the mean µ and derivative $$\sigma$$:

$$µ = \frac{\sum_{n \in N} n}{| N |} \quad \sigma = \sqrt{\frac{ \sum_{n \in N} (n - µ )^2 }{| N |}}$$

The cumulative distribution function CDF is the integral over the PDF and creates a uniform random distributed output for the elements in the initial distribution. The reason for the uniformity is based on a phenomena called probability integral transform. In the case of normal distribution the CDF is closely related to the errorfunction, BUT NOT exactly the error function. A mistake that took me way too long to realise. The CDF is as follows:

$$f(x) = \frac{1}{2} * (1 + erf(\frac{x - µ}{\sigma \sqrt 2}))$$

where $$erf$$ refers to the error function. Last but not least we want buckets and because we have an integral over probability, we only have values between 0 and 1. We can simply rescale using the number of buckets and we are done. This way, we can build a bucket sort for normal/gaussian distribution which is still in $$O(n)$$. My result:

import math
import scipy.stats

def bucket_sort(numbers, mean, deviation):
# Just recompute here to see what happens
mean = sum(numbers) / len(numbers)
variance = sum((x - mean) ** 2 for x in numbers) / len(numbers)
deviation = math.sqrt(variance)

num_buckets = int( math.sqrt(len(numbers)) )
buckets = [[] for _ in range(num_buckets)]

for num in numbers:
# index = scipy.stats.norm.cdf(num, mean, deviation)
tmp = (num - mean)/(deviation*math.sqrt(2))
index = 0.5 *(1+math.erf(tmp))
index = int(index * num_buckets)

# Append rescaled value to bucket
buckets[index].append(num)

for bucket in buckets:
bucket.sort()

sorted_numbers = [num for bucket in buckets for num in bucket]

return sorted_numbers

# example call
mean = 50
std = 20
input = scipy.stats.norm.rvs(50,20,100)
input = [int(i) for i in input]
print(bucket_sort(input,mean, std))


I am not quite sure whether I should thank Yves Daoust or not :D At least he tried to help me, which I appreciate a lot, but I am sorry, your input wasn't quite helpful. What helped me a lot, was this post.