Bucket Sort Algorithm (Java, Python, C/C++ Code Examples)

⚡ Smart Summary

Bucket Sort scatters input elements into several buckets, sorts each bucket independently, and gathers them to produce a final sorted array.

🪣 Core Idea: Bucket Sort divides values across buckets, sorts each, then concatenates them in order.
📊 Best Fit: Bucket Sort works best on uniformly distributed floats in [0.0, 1.0] or evenly spread integers.
⚡ Time Complexity: Average and best cases reach O(n+k) linear time; worst case degrades to O(n²).
✅ Advantages: Buckets can be processed in parallel, suitable for external sorting of large datasets.
🧪 Implementation: Code in C, C++, Python, and Java demonstrates both floating-point and integer variants.

What is Bucket Sort?

Bucket Sort, often called bin sort, is a comparison-based distribution sorting method that accepts an unsorted array as input and produces a sorted array as output. This technique distributes elements into several buckets and sorts each bucket individually using another sorting algorithm such as insertion sort. Then, all the buckets are merged together to form the final sorted array.

Bucket Sort is commonly used when the elements are:

Floating-point values
Uniformly distributed over a known range

The time complexity of Bucket Sort depends on the number of buckets used and the uniformity of the input distribution. While other sorting algorithms such as shell sort, merge sort, heapsort, and quicksort achieve a best-case time complexity of O(n*logn), the Bucket Sort algorithm can reach linear time complexity O(n) under favorable conditions.

Bucket Sort follows the scatter-gather approach. Elements are scattered into corresponding buckets, sorted inside each bucket, and gathered to form a sorted array as the final step. This scatter-gather approach is discussed in the following section.

Scatter-Gather Approach

Large-scale, complex problems can occasionally be challenging to solve directly. The scatter-gather approach addresses such problems by dividing the entire dataset into clusters. Each cluster is processed separately, and the results are brought back together to produce the final answer.

Here is how the Bucket Sort algorithm implements the scatter-gather method:

How Bucket Sort Works

The basic working principle of Bucket Sort is as follows:

A set of empty buckets is created. Based on the policy chosen, the number of buckets can vary.
From the input array, each element is placed into its corresponding bucket.
Each bucket is sorted individually using a secondary sorting algorithm.
The sorted buckets are concatenated to produce a single output array.

Pseudo Code

Start
Create N empty buckets
For each array element:
    Calculate bucket index
    Put that element into the corresponding bucket
For each bucket:
    Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

Method 1: Bucket Sort Algorithm for Floating-Point Numbers

The Bucket Sort algorithm for floating-point numbers within the range [0.0, 1.0]:

Step 1) Create ten (10) empty buckets. The first bucket holds numbers within the range [0.0, 0.1). The second bucket holds [0.1, 0.2), and so on.

Step 2) For each array element:

a. Calculate the bucket index using the formula:
bucket_index = no_of_buckets * array_element
b. Insert the element into bucket[bucket_index]

Step 3) Sort each bucket individually using insertion sort.

Step 4) Concatenate all buckets into a single sorted array.

Let us walk through a Bucket Sort example. For this example, we will sort the following array:

Step 1) First, we create 10 empty buckets. The first bucket holds numbers in [0.0, 0.1). The second bucket holds [0.1, 0.2), and so on.

Step 2) For each array element, calculate the bucket index and place the element into that bucket.

The bucket index is calculated using the formula:
bucket_index = no_of_buckets * array_element

Bucket Index Calculation:
a) 0.78
      bucket_index = no_of_buckets * array_element
              = 10 * 0.78
              = 7.8
Hence, the element 0.78 is stored in bucket[floor(7.8)] or bucket[7].

b) 0.17
      bucket_index = no_of_buckets * array_element
              = 10 * 0.17
              = 1.7

The array element 0.17 is stored in bucket[floor(1.7)] or bucket[1].

c) 0.39
      bucket_index = no_of_buckets * array_element
              = 10 * 0.39
              = 3.9
0.39 is stored in bucket[floor(3.9)] or bucket[3].

After iterating over all array elements, the buckets look as follows:

Step 3) Each bucket is then sorted using insertion sort. After the sorting operation, the output is:

Step 4) In the final step, the buckets are concatenated into a single array. That array is the sorted outcome of the input.

Each bucket is concatenated to the output array. For example, the concatenation of the second bucket elements:

The concatenation of the last bucket elements is shown below:

After concatenation, the resulting array is the desired sorted array.

Bucket Sort Program in C/C++

Input:

//Bucket Sort Program in C/C++
//For values without integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
  for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
    bucket[index].push_back(input[i]);
  }
  for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
  float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
  int array_size = sizeof(input)/sizeof(input[0]);

  bucketSort(input, array_size);
  cout <<"Sorted Output: 
";
  for (int i = 0; i< array_size; i++)
    cout<<input[i]<<" ";
  return 0;
}

Output:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Bucket Sort Program in Python

Input:

# Bucket Sort Program in Python
# For values without integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

Output:

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

Bucket Sort in Java

Input:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List<Float>[] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList<>();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
                }
            }
        }
    }
    public static void main(String[] args) {
        float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

Output:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Method 2: Bucket Sort Algorithm for Integer Elements

The Bucket Sort algorithm for input that contains numbers beyond the range [0.0, 1.0] is slightly different from the previous algorithm. The steps required for this case are as follows:

Step 1) Find the maximum and minimum elements in the array.

Step 2) Select the number of buckets, n, and initialize them as empty.

Step 3) Calculate the range or span of each bucket using the formula:
span = (maximum - minimum) / n

Step 4) For each array element:

1. Calculate the bucket index:
bucket_index = (element - minimum) / span
2. Insert the element into bucket[bucket_index]

Step 5) Sort each bucket using insertion sort.

Step 6) Concatenate all the buckets into a single array.

Let us walk through an example of this Bucket Sort algorithm. For this example, we will sort the following array:

Step 1) In the first step, we find the maximum and minimum elements of the given array. For this example, the maximum is 24 and the minimum is 1.

Step 2) Next, we select the number of empty buckets, n. In this example, we use 5 buckets and initialize them as empty.

Step 3) The span of each bucket is calculated using the formula:
span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Hence, the first bucket holds numbers within [0, 5). The second bucket holds [5, 10), and so on.

Step 4) For each array element, calculate the bucket index and place the element into that bucket. The bucket index is calculated using the formula:
bucket_index = (element - minimum) / span

Bucket Index Calculation:

a) 11
bucket_index = (element – minimum) / span
= (11 – 1) / 4
= 2

Thus, element 11 is stored in bucket[2].

b) 9
bucket_index = (element – minimum) / span
= (9 – 1) / 4
= 2

Note: As 9 is a boundary element for bucket[1], it is appended to bucket[1] instead of being placed in the same bucket as the previous element.

After performing the operations for each element, the buckets look as follows:

Step 5) Now, each bucket is sorted using insertion sort. The buckets after sorting:

Step 6) In the final step, the buckets are concatenated into a single array. That array is the sorted outcome of the input.

Bucket Sort Program in C/C++

Input:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>> output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     - int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1].push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double> input ={11,9,21,8,17,19,13,1,24,12};
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<"Sorted Output:";
  for (int i=0; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

Output:

Sorted Output:1 8 9 11 12 13 17 19 21 24

Bucket Sort Program in Python

Input:

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:
", input)

Output:

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

Bucket Sort in Java

Input:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List<List<Double>> output = new ArrayList<>();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList<>());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
            }
        }
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double> input = new ArrayList<>();
        input.add(11.0);
        input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
            System.out.print(value + " ");
        }
    }
}

Output:

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

Pros & Cons of Bucket Sort

Pros	Cons
Performs faster computation on uniformly distributed data	Consumes more space compared to in-place sorting algorithms
Can be used as an external sorting method for large datasets	Performs poorly when the data is not uniformly distributed
Buckets can be processed independently and in parallel	Requires knowledge of the data range and distribution upfront

Bucket Sort Complexity Analysis

Bucket Sort Time Complexity

Best Case Complexity: If all the array elements are uniformly distributed and pre-sorted within each bucket, it requires O(n) time to scatter the elements into the corresponding buckets. Then sorting each bucket using insertion sort costs O(k). Thus the overall complexity is O(n+k).
Average Case Complexity: For average cases, we assume the inputs are uniformly distributed. Thus the Bucket Sort algorithm achieves a linear time complexity of O(n+k). Here, O(n) time is required for scattering the elements and O(k) time is required for sorting them using insertion sort.
Worst Case Complexity: In the worst case, the elements are not uniformly distributed and concentrate in one or two buckets. In that case, Bucket Sort degrades to behavior similar to a bubble sort algorithm. Hence, in the worst case, the time complexity of Bucket Sort is O(n²).

Space Complexity of Bucket Sort

The space complexity of Bucket Sort is O(n*k). Here, n is the number of elements and k is the number of buckets required to hold them during sorting.

FAQs

Use Bucket Sort when input values are uniformly distributed across a known range, especially floating-point numbers in [0.0, 1.0]. It delivers linear time on such data but performs poorly on clustered or unknown distributions.

Bucket Sort is stable when the inner sorting algorithm used inside each bucket is stable. Insertion sort preserves the relative order of equal elements, so the standard Bucket Sort implementation using insertion sort is considered stable.

Bucket Sort groups elements by value range and sorts each bucket with another algorithm. Radix Sort groups numbers digit by digit and uses counting sort internally. Bucket Sort favors uniformly distributed floats; Radix Sort favors fixed-width integers or strings.

The worst-case time complexity of Bucket Sort is O(n²). This occurs when all input elements fall into a single bucket, forcing the inner sort (typically insertion sort) to behave quadratically. Uniform distribution avoids this scenario.

Yes. To handle negatives, find both the minimum and maximum, then compute the bucket index using (element – minimum) / span. This shifts negative values into a non-negative index space and lets the standard Bucket Sort logic proceed unchanged.

AI-powered platforms such as VisuAlgo, Algorithm Visualizer, and ChatGPT-generated step-by-step traces help learners visualize Bucket Sort. They animate scatter, sort, and gather phases, making the bucket index math and partitioning logic easier to grasp.

AI-driven recommenders analyze dataset size, value distribution, and memory limits to suggest a fitting algorithm. For uniformly distributed floats, such systems favor Bucket Sort. For mixed integer ranges, they may suggest quicksort or Radix Sort instead.

Bucket Sort Algorithm (Java, Python, C/C++ Code Examples)

What is Bucket Sort?

Scatter-Gather Approach

How Bucket Sort Works

Pseudo Code

Method 1: Bucket Sort Algorithm for Floating-Point Numbers

Bucket Sort Program in C/C++

Bucket Sort Program in Python

Bucket Sort in Java

Method 2: Bucket Sort Algorithm for Integer Elements

Bucket Sort Program in C/C++

Bucket Sort Program in Python

Bucket Sort in Java

Pros & Cons of Bucket Sort

Bucket Sort Complexity Analysis

Bucket Sort Time Complexity

Space Complexity of Bucket Sort

FAQs

Summarize this post with:

Sign up for the newsletter

What is Bucket Sort?

Scatter-Gather Approach

How Bucket Sort Works

Pseudo Code

Method 1: Bucket Sort Algorithm for Floating-Point Numbers

RELATED ARTICLES

Bucket Sort Program in C/C++

Bucket Sort Program in Python

Bucket Sort in Java

Method 2: Bucket Sort Algorithm for Integer Elements

Bucket Sort Program in C/C++

Bucket Sort Program in Python

Bucket Sort in Java

Pros & Cons of Bucket Sort

Bucket Sort Complexity Analysis

Bucket Sort Time Complexity

Space Complexity of Bucket Sort

FAQs

Summarize this post with:

Sign up for the newsletter