Bucket Sort Algorithm with Solved Example

Sorting is an important part of computer science because it helps us arrange data in the correct order. When data is sorted, it becomes easy to search, compare, and process. One such smart and efficient sorting method is Bucket Sort. This algorithm works by placing elements into small groups called buckets and then sorting each bucket separately. After that, all buckets are joined together to form the final sorted list.

Bucket Sort is very fast when the input values are spread evenly within a known range. It is commonly used for sorting decimal numbers, percentages, and data that falls between 0 and 1. In this blog, we will learn what Bucket Sort is, how it works, its steps, example, time and space complexity, advantages, disadvantages, applications, and a complete Java program to help you understand it clearly.

What is Bucket Sort?

Bucket Sort is a sorting algorithm that works by dividing elements into different groups called buckets.
Each bucket holds elements in a specific range. After that, each bucket is sorted using another sorting method (like Insertion Sort). Finally, all buckets are joined to form the final sorted list.

It works best when:

• Data is uniformly distributed
• Range of values is known
• We need fast sorting of decimal or floating-point numbers

Bucket Sort Working

1. Find the Range of Numbers

First, look at your list and find the smallest and largest numbers. This helps you know how many buckets you need and what range each bucket will cover.

2. Create Empty Buckets

Make a few empty buckets (like small containers). Each bucket will hold numbers that fall within a certain range. For example, if your numbers are between 0 and 1, you might create 10 buckets — one for 0–0.1, another for 0.1–0.2, and so on.

3. Put Numbers into Buckets

Go through the list and place each number into the right bucket based on its value. For example, 0.23 goes into the 0.2–0.3 bucket, and 0.76 goes into the 0.7–0.8 bucket.

4. Sort Each Bucket

Now, sort the numbers inside each bucket. You can use another simple sorting algorithm like Insertion Sort for this, since each bucket will have only a few elements.

5. Combine All Buckets

After sorting all the buckets, join (concatenate) them one by one from smallest to largest range. This gives you the final sorted list.

Example of Bucket Sort

Let’s take an easy example to understand how Bucket Sort works clearly.

Input Array:

[0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]

We are sorting numbers between 0 and 1.

Step 1: Create Buckets

Make 7 empty buckets (because we have 7 numbers).

Initially, all buckets are empty:

Bucket 0: [ ]
Bucket 1: [ ]
Bucket 2: [ ]
Bucket 3: [ ]
Bucket 4: [ ]
Bucket 5: [ ]
Bucket 6: [ ]

Step 2: Distribute Elements

Put every number into its bucket:

Number	Bucket Index (value × 7)	Goes to Bucket
0.42	2.94 → 2	Bucket 2
0.32	2.24 → 2	Bucket 2
0.23	1.61 → 1	Bucket 1
0.52	3.64 → 3	Bucket 3
0.25	1.75 → 1	Bucket 1
0.47	3.29 → 3	Bucket 3
0.51	3.57 → 3	Bucket 3

Buckets After Distribution

Bucket 1 → [0.23, 0.25]

Bucket 2 → [0.32, 0.42]

Bucket 3 → [0.47, 0.51, 0.52]

Step 3: Sort Each Bucket

Sort each bucket using Insertion Sort:

After sorting:

Bucket 0: [ ]
Bucket 1: [0.23, 0.25]
Bucket 2: [0.32, 0.42]
Bucket 3: [0.47, 0.51, 0.52]
Bucket 4: [ ]
Bucket 5: [ ]
Bucket 6: [ ]

Step 4: Combine All Buckets

Finally, join all the sorted buckets one by one to form the final sorted list.

Final Sorted Array:

[0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]

Algorithm Steps of Bucket Sort

1. Create Buckets:
   • First, decide how many buckets you need. The number of buckets usually depends on the size or range of your input data.
   • Then, make empty buckets (like small containers or lists).
   • Each bucket will store elements that fall within a certain range of values.
   • For example, if you are sorting numbers between 0 and 1, and you create 10 buckets, then:
     • Bucket 1 → numbers from 0.0 to 0.1
     • Bucket 2 → numbers from 0.1 to 0.2
     • … and so on up to 1.0
2. Distribute Elements:
   • Now, go through the input list and place each element into the correct bucket based on its value.
   • To find which bucket a number belongs to, you can multiply it by the total number of buckets (for numbers between 0 and 1).
   • Example: if the number is 0.43 and you have 10 buckets, it goes into bucket number 4 (since 0.43 × 10 = 4.3 → bucket 4).
   • After this step, every bucket will have numbers that are close in value.
3. Sort Each Bucket:
   • Next, sort the numbers inside each bucket.
   • You can use Insertion Sort, Quick Sort, or any simple sorting algorithm for this step.
   • Since each bucket has fewer elements, sorting them takes very little time.
   • After sorting, all numbers in each bucket are arranged in increasing order.
4. Combine Buckets:
   • Finally, go through all the buckets in order (from smallest range to largest range) and join their contents together.
   • Combine the sorted numbers from each bucket into one final list.
   • This gives you a completely sorted array of all elements.

Bucket Sort Implementation Using C++

#include <iostream>
#include <vector>
#include <algorithm> // for sort()
using namespace std;

// Function to perform Bucket Sort
void bucketSort(float arr[], int n) {
    // 1. Create n empty buckets
    vector<float> buckets[n];

    // 2. Put array elements into different buckets
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * arr[i];  // Find the bucket index (works for numbers between 0 and 1)
        buckets[bucketIndex].push_back(arr[i]);
    }

    // 3. Sort each bucket individually
    for (int i = 0; i < n; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // 4. Combine all buckets into the original array
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    // Input array (values between 0 and 1)
    float arr[] = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    // Call bucket sort
    bucketSort(arr, n);

    cout << "Sorted array:   ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

Output

Original array: 0.42 0.32 0.23 0.52 0.25 0.47 0.51 
Sorted array:   0.23 0.25 0.32 0.42 0.47 0.51 0.52

Explanation of code

The above C++ program uses the bucketSort() function to sort floating-point numbers between 0 and 1. Inside the function, it first creates n empty buckets using vector<float> buckets[n];. Then, a for loop runs through each element of the array arr[], calculating the correct bucket index with the formula int bucketIndex = n * arr[i]; and placing the element inside that bucket using buckets[bucketIndex].push_back(arr[i]);.

Next, another for loop sorts each bucket individually using the built-in sort() function. After sorting, it uses a nested for loop to combine all the buckets back into the original array with arr[index++] = buckets[i][j];. In the main() function, the array arr[] is declared, and its size is found using sizeof(arr) / sizeof(arr[0]);. The program then prints the original array, calls the bucketSort() function, and finally prints the sorted array.

Time Complexity of Bucket Sort

Case	Time Complexity
Best Case	O(n + k)
Average Case	O(n + k)
Worst Case	O(n²)

Space Complexity of Bucket Sort

Case	Time Complexity
Best Case	O(n + k)
Average Case	O(n + k)
Worst Case	O(n + k)

Advantages of Bucket Sort

• Stable Sorting (if using stable sub-sort):
  If a stable sorting algorithm like Insertion Sort is used inside the buckets, the entire Bucket Sort becomes stable.
• Highly Efficient for Uniform Data:
  Bucket Sort works very fast when the input data is uniformly distributed, such as numbers between 0 and 1.
• Can Achieve Linear Time Complexity:
  In the best case, it can sort data in O(n + k) time, which is faster than comparison-based algorithms like Merge Sort or Quick Sort.
• Simple and Easy to Understand:
  The concept of dividing elements into buckets and sorting them individually is easy to visualize and implement.
• Useful for Floating-Point Numbers:
  Bucket Sort handles decimal or fractional numbers effectively, which is difficult for some other sorting algorithms.
• Parallel Processing Friendly:
  Each bucket can be sorted independently, making it suitable for parallel or multi-threaded execution.

Disadvantages of Bucket Sort

• Overhead in Bucket Management:
  Creating, distributing, and merging buckets adds additional overhead in both time and space.
• Not Suitable for Non-Uniform Data:
  If the data is not evenly distributed, some buckets may have too many elements while others remain empty, leading to poor performance.
• Extra Space Requirement:
  It requires O(n + k) extra space for storing buckets, making it less memory-efficient.
• Difficult to Implement for Large Ranges:
  If the range of data values is large, deciding the number and size of buckets becomes complex.
• Depends on Sub-Sorting Algorithm:
  The overall efficiency depends on how efficiently each bucket is sorted.
• Not Ideal for Integer Sorting:
  Counting Sort or Radix Sort performs better for integers, while Bucket Sort is mainly for floating-point numbers.

Applications of Bucket Sort

1. Sorting decimal or floating-point numbers
2. Used in computer graphics for color sorting
3. Used when values fall between a known range
4. Used in probability-based systems
5. Used for sorting marks, percentages, or metrics
6. Perfect for normalized datasets (0 to 1 range)