Bucket Sort Algorithm: Python & JavaScript Implementation

Introduction

Sorting is a fundamental operation in computer science, and choosing the right algorithm can significantly impact performance. Bucket Sort can be highly efficient when the input data is uniformly distributed across a known range, as this ensures elements are spread evenly among buckets. However, its performance can degrade significantly if the data is skewed or clustered, leading to uneven bucket sizes and slower sorting within individual buckets. In this blog, we will explore

What is Bucket Sort?
How Bucket Sort Works (Step-by-Step)
Bucket Sort Example (With Walkthrough)
Bucket Sort Algorithm and Code Examples
- 4.1 Bucket Sort in Python
- 4.2 Bucket Sort in JavaScript
Computational Complexity and Sublist Memory Usage
Advantages of Bucket Sort
Disadvantages of Bucket Sort
When Should You Use Bucket Sort?
Bucket Sort vs Other Sorting Algorithms
Real-World Applications of Bucket Sort
Frequently Asked Questions about 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 (Step-by-Step)

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.

Bucket Sort Example (With 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]

Scatter and Gather Phases in Bucket Sort

The Bucket Sort algorithm can be divided into two main phases:

Scatter Phase: Each element is placed into its respective bucket based on its value and a calculated bucket index. This index is usually derived using the formula:
bucketIndex = floor(n * array[i]),
where n is the number of buckets and array[i] is the value.
Gather Phase: After individual buckets are sorted using a stable sorting algorithm like Insertion Sort, they are concatenated to produce the final sorted array.

These two phases form the core of how Bucket Sort efficiently organizes and sorts data across a known range.

Pseudocode for Bucket Sort

Here's the language-independent pseudocode representation of the Bucket Sort algorithm to help you understand its flow clearly:

function bucketSort(array, n):
    create n empty buckets

    for i in 0 to length(array) - 1:
        index = floor(n * array[i]) // scatter phase
        insert array[i] into buckets[index]

    for each bucket:
        sort bucket using a stable sorting algorithm (e.g., insertion sort)

    concatenate all buckets into sorted_array // gather phase
    return sorted_array

This pseudocode highlights how Bucket Sort uses bucket indexing, stable sorting within sublists, and concatenation to complete the sorting process.

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]))

Computational Complexity and Sublist Memory Usage

The computational complexity of Bucket Sort depends on the input distribution, the number of buckets, and the sorting method used within each bucket.

Best Case: O(n + k) when elements are evenly distributed and insertion sort is used.
Average Case: Still O(n + k) under ideal conditions.
Worst Case: O(n²) if all elements cluster into one bucket (similar to Insertion Sort).

In terms of space, the worst-case space complexity is O(n + k), where n is the number of elements and k is the number of buckets. This includes temporary memory used for buckets and internal sublists during sorting.

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 or Skewed Ranges: If the input data is not uniformly distributed or spans a very large range, many elements may cluster into a few buckets. This results in some buckets containing far more elements than others, negating the efficiency of the algorithm and potentially reducing performance to that of slower sorting methods.
Complex Implementation: More intricate than simpler sorts like Insertion Sort.

Optimizations and Variants of Bucket Sort

Several optimized versions of Bucket Sort have been developed to improve its performance and adaptability:

ProxmapSort: Attempts to eliminate sorting within buckets by calculating the exact or near-exact position of each item.
Histogram Sort: Works by counting the number of items that fall into each bucket, making it highly efficient for visual data distributions and analytics.
Generic Bucket Sort: An extended version that adapts to various input types and custom-defined bucket logic.
Pigeonhole Sort: A similar distribution-based algorithm optimized for small integer ranges.

These optimizations trade additional auxiliary space and setup logic for faster performance, especially when dealing with structured numeric inputs and known value ranges.

When Should You 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:

The data is highly skewed or clustered, as this leads to uneven bucket distribution and poor performance.
Available memory is limited, since Bucket Sort requires additional space for storing buckets.
The elements cover a vast range, making it difficult to allocate buckets efficiently and evenly.

Bucket Sort vs Other Sorting Algorithms

Choosing the right sorting algorithm often depends on the nature of the data, distribution, and specific use case. Here's how Bucket Sort compares to other popular algorithms:

Bucket Sort vs Quick Sort

Quick Sort is a general-purpose, comparison-based algorithm with an average time complexity of O(n log n). It performs well on most datasets but can degrade to O(n²) in the worst case.
Bucket Sort, on the other hand, can achieve linear time complexity O(n + k) when elements are uniformly distributed. However, its efficiency drops significantly if data is skewed.

Use Bucket Sort when data is uniformly distributed over a known range (e.g., 0 to 1).
Use Quick Sort when you need a fast, general-purpose sort that doesn't rely on data distribution.

Bucket Sort vs Merge Sort

Merge Sort is a stable, divide-and-conquer algorithm with consistent O(n log n) time complexity, regardless of data distribution. It is reliable and predictable for any dataset.
Bucket Sort offers potentially faster performance for specific datasets (e.g., decimal values with even spread) but requires more space and customization.

Use Bucket Sort when dealing with well-distributed floating-point numbers.
Use Merge Sort when consistency and stability are more important than raw speed.

Bucket Sort vs Counting Sort

Counting Sort is extremely efficient (O(n + k)) for sorting integers within a limited range but does not work well for floating-point or negative values.
Bucket Sort is more flexible, especially for real numbers and decimal data, but needs more memory and setup.

Use Bucket Sort when working with non-integer data over a known range.
Use Counting Sort when sorting small-range integers and memory is not a constraint.

Bucket Sort vs Radix Sort

Radix Sort is a non-comparison algorithm ideal for fixed-length integer or string data. It's often faster than comparison-based sorts for those cases.
Bucket Sort may outperform Radix Sort on floating-point datasets that are evenly distributed.

Use Bucket Sort when sorting real numbers like probabilities, scores, or measurements.
Use Radix Sort when sorting long lists of integers or strings with known length.

Quick Comparison Table

Algorithm	Best For	Time Complexity (Best/Average/Worst)	Space Complexity	Stability
Bucket Sort	Uniformly distributed floats/decimals	O(n + k) / O(n + k) / O(n²)	O(n + k)	Yes
Quick Sort	General-purpose sorting	O(n log n) / O(n log n) / O(n²)	O(log n)	No
Merge Sort	Stable sorting, large datasets	O(n log n) / O(n log n) / O(n log n)	O(n)	Yes
Counting Sort	Integers in a small range	O(n + k) / O(n + k) / O(n + k)	O(k)	Yes
Radix Sort	Integers, fixed-length strings	O(nk) / O(nk) / O(nk)	O(n + k)	Yes

Real-World Applications of Bucket Sort

Bucket Sort isn’t just something you learn in an algorithms class—it actually shines in some very real and practical situations, especially when your data is nicely spread out.

Where Bucket Sort Really Works

Sorting percentages or probabilities: Got numbers between 0 and 1? Perfect. Bucket Sort was made for this. Whether it’s probability values or percentages, it handles them with ease.
Grading systems: Think student scores—if you’re dividing them into ranges like A, B, C, and so on, Bucket Sort can quickly group and sort them.
Age or income group segmentation: Planning to break down users by age brackets or income levels? Bucket Sort is a great fit for that kind of categorized data.
Data that's already normalized: In many machine learning or analytics tasks, data is pre-normalized. Bucket Sort can handle this kind of structured input efficiently.
Generating histograms: If you’re plotting data into frequency intervals, Bucket Sort can help organize those ranges quickly and cleanly.

A Few Smart Tweaks

There are also some optimized versions of Bucket Sort that make it even more powerful:

ProxmapSort: A fancy variant that skips sorting inside the buckets by figuring out exactly where each item should go.
Histogram Sort: Focuses more on counting how many items fall into each bucket, which is great for things like analytics and visualization.
Custom bucket ranges: If you already know how your data is spread, you can tweak your bucket boundaries to keep the distribution even—and the algorithm fast.

Frequently Asked Questions about Bucket Sort

Q1. Is Bucket Sort stable?

Yes, Bucket Sort can be made stable by using a stable sorting algorithm (such as Insertion Sort) within each bucket. This ensures that elements with equal values retain their original relative order after sorting.

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.

Conclusion

Bucket Sort is a powerful algorithm when applied correctly. When input data is uniformly distributed and the range is known, Bucket Sort can outperform traditional comparison-based algorithms like Quick Sort or Merge Sort due to its potential for linear time complexity. However, for datasets with unknown or highly variable distributions, Quick Sort or Merge Sort are generally more reliable because they do not rely on data distribution and maintain consistent performance regardless of input.

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