Bucket Sort Algorithm: How It Works & When to Use It

Introduction

Sorting is a fundamental operation in computer science, and choosing the right algorithm can significantly impact performance. Bucket Sort is an efficient sorting technique that excels when dealing with a uniform distribution of numbers. In this blog, we will explore what Bucket Sort is, how it works, its time complexity, advantages, disadvantages, and implementation in JavaScript and Python.

What is Bucket Sort?
How Does Bucket Sort Work?
Step-by-Step Implementation of Bucket Sort
Bucket Sort Algorithm with Code Examples
- 4.1 Bucket Sort in Python
- 4.2 Bucket Sort in JavaScript
Time Complexity of Bucket Sort
Space Complexity of Bucket Sort
Advantages and Disadvantages of Bucket Sort
When to Use Bucket Sort?
Bucket Sort vs Other Sorting Algorithms
Real-World Applications of Bucket Sort
Conclusion

What is Bucket Sort?

Bucket Sort is a comparison-based sorting algorithm that distributes elements into multiple “buckets,” sorts each bucket individually, and then merges them to produce the final sorted array.

It works best when input data is uniformly distributed over a known range, making it particularly efficient for floating-point numbers, percentages, or large datasets with minimal variation.

How Bucket Sort Works

The Bucket Sort algorithm follows these steps:

Create Buckets: Divide the input elements into a fixed number of buckets.
Distribute Elements: Place each element into its respective bucket based on a calculated index.
Sort Individual Buckets: Sort each bucket using an appropriate algorithm (Insertion Sort, Merge Sort, or Quick Sort).
Concatenate Buckets: Combine the sorted buckets to get the final sorted array.

Example Walkthrough

Let’s say we need to sort the array [0.42, 0.32, 0.77, 0.25, 0.61, 0.89] using Bucket Sort:

Create Buckets: Assume 5 buckets for values ranging from 0 to 1.
Distribute Elements:
- Bucket 1: [0.25]
- Bucket 2: [0.32, 0.42]
- Bucket 3: [0.61]
- Bucket 4: [0.77]
- Bucket 5: [0.89]
Sort Buckets:
- Bucket 2: [0.32, 0.42] (sorted using Insertion Sort)
Concatenate Buckets:[0.25, 0.32, 0.42, 0.61, 0.77, 0.89]

Time Complexity of Bucket Sort

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

n = number of elements
k = number of buckets

The best and average cases occur when elements are distributed evenly across buckets, and sorting each bucket is efficient. The worst case occurs when all elements fall into a single bucket, making Bucket Sort equivalent to O(n^2) sorting algorithms like Bubble Sort.

Advantages of Bucket Sort

Fast for Uniformly Distributed Data: Works efficiently when elements are evenly spread.
Efficient for Floating-Point Numbers: Handles fractional values well.
Can Leverage Other Sorting Algorithms: Buckets can use efficient sorts like Quick Sort or Merge Sort.
Parallelizable: Sorting individual buckets can be done concurrently.

Disadvantages of Bucket Sort

Requires Extra Space: Needs additional storage for buckets.
Not Suitable for Large Range Inputs: Performance suffers when data is not uniformly distributed.
Complex Implementation: More intricate than simpler sorts like Insertion Sort.

Bucket Sort Implementation in JavaScript

function bucketSort(arr, bucketSize = 5) {
    if (arr.length === 0) return arr;

    let min = Math.min(...arr);
    let max = Math.max(...arr);
    let bucketCount = Math.floor((max - min) / bucketSize) + 1;
    let buckets = Array.from({ length: bucketCount }, () => []);

    arr.forEach(num => {
        let index = Math.floor((num - min) / bucketSize);
        buckets[index].push(num);
    });

    return buckets.reduce((sortedArr, bucket) => {
        return sortedArr.concat(bucket.sort((a, b) => a - b));
    }, []);
}

console.log(bucketSort([42, 32, 77, 25, 61, 89]));

Bucket Sort Implementation in Python

def bucket_sort(arr, bucket_size=5):
    if len(arr) == 0:
        return arr
    
    min_val, max_val = min(arr), max(arr)
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    for num in arr:
        index = (num - min_val) // bucket_size
        buckets[index].append(num)
    
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))
    
    return sorted_arr

print(bucket_sort([42, 32, 77, 25, 61, 89]))

When to Use Bucket Sort?

✅ Best Use Cases:

When input data is uniformly distributed.
When sorting floating-point numbers or decimal values.
When dealing with large datasets and can leverage parallel processing.

❌ Avoid When:

Data is highly skewed (non-uniform distribution).
Memory is limited (extra space required for buckets).
Elements range over a wide interval, making bucket allocation inefficient.

Conclusion: Should You Use Bucket Sort?

Bucket Sort is a powerful algorithm when applied correctly. If your dataset has a uniform distribution and can fit into a predefined range, it can outperform many traditional sorting methods. However, for general-purpose sorting, algorithms like Quick Sort or Merge Sort might be better choices.

If you are working with floating-point numbers, percentages, or large datasets with uniform distribution, Bucket Sort is an excellent choice for optimal performance.

FAQs on Bucket Sort

Q1. Is Bucket Sort stable?

Yes, Bucket Sort can be stable if elements in each bucket maintain their original order when sorted.

Q2. What is the best case time complexity of Bucket Sort?

The best case occurs when elements are evenly distributed, leading to O(n + k) time complexity.

Q3. Can Bucket Sort be used for negative numbers?

Yes, but additional logic is needed to handle negative values when distributing elements into buckets.

Q4. Is Bucket Sort better than Quick Sort?

It depends on the dataset. Quick Sort is generally faster for general sorting, while Bucket Sort excels with uniformly distributed data.

Bucket Sort Algorithm: How It Works & When to Use It

Introduction

Table of Contents