Sort a series of n numbers between [0,2k], Where between each pair exists: |Ai-Aj|>=k/n

Question

Let A1,A2,...,An be real numbers between [0,2k] (k is constant). It's known that for any pair of Ai,AJ then |Ai-Aj|>=k/n,

Describe an algorithm sorting the numbers in O(n) runtime worst-case.

I know that the answer should be bucket-sort. Can't understand why, And if so, How do I choose the correct amount of buckets? How does the |Ai-Aj|>=k/n actually helps?

Answer 1

The condition |A_i - A_j| ≥ k / n means that if you divide the range [0, 2k] into 2n different buckets (each of which has size 2k / 2n = k / n), then there can be at most one number in each range (except possibly if the numbers are at the endpoints of the buckets.) If you create the buckets more tightly (say, by creating 3n buckets), then each bucket has size less than k / n and therefore can contain at most one number.

You could then sort the numbers by using a bucket sort algorithm:

• Create an array of 3n buckets, each representing the range [(2k / 3n)i, (2k / 3n)(i + 1))
• For each number:
  • Divide that number by (2k / 3n) to determine which bucket to place it into.
  • Place the number in that bucket.
• For each bucket:
  • If that bucket is nonempty, write the number in that bucket into the result array.

The first step takes O(n) time, since you're creating an array of size 3n. The next step takes time O(n), since you visit each of the O(n) numbers once and do O(1) work at each step. The final step also takes O(n) time, since you're visiting a total of 3n buckets.

Hope this helps!