Bucket Sort Algorithm: Overview, Time Complexity & Pseudocode

TL;DR: Bucket sort distributes array elements into buckets by value, sorts each bucket, then gathers them back in order. It runs in O(n + k) time when data is uniformly distributed, but O(n²) in the worst case. This guide includes a worked example and verified code in C, C++, Java, and Python. It's best suited for large, evenly distributed datasets.

Bucket sort is an advanced sorting technique compared with others. Bucket sort can be considered a collective framework built using a variety of sorting algorithms. For example, you can use one type of algorithm to sort elements into buckets and another to sort elements within buckets. You could even recursively implement the algorithm you initially chose to sort each bucket to minimize lines of code.

Because of this adaptability, bucket sorting becomes slightly more complex but also the most versatile.

What Is a Bucket Sort Algorithm?

Bucket sort, also known as bin sort, is a sorting algorithm that divides an array's elements into several buckets. It then sorts the buckets one at a time, either using a different sorting algorithm or by recursively applying bucket sort.

The bucket sort method is as follows:

• Create an array of "buckets" that are initially empty
• Scatter: go through the original array, placing each element in its appropriate bucket
• Sort each non-empty bucket
• Gather: return all elements to the original array by visiting the buckets in order.

In this tutorial, you will learn how the bucket sort algorithm works.

Working of a Bucket Sort Algorithm

The bucket sort algorithm works as follows:

• Make a one-dimensional array of empty buckets. Each slot represents one bucket, and the number of buckets is typically chosen to match the number of elements you're sorting.
• Insert array elements into the buckets, based on the bucket's range. If your input values are floats between 0 and 1, and you have 10 buckets, then bucket 0 holds values from 0 to 0.1, bucket 1 holds 0.1 to 0.2, and so on up to bucket 9.
• To figure out which bucket a value belongs in, multiply it by the number of buckets and take the floor of the result. For example, with 10 buckets, a value of 0.34 becomes floor(0.34 * 10), which is 3, so 0.34 goes into bucket 3.
• Sort each bucket's elements using a stable sorting algorithm, typically insertion sort, since buckets tend to be small.
• Gather all the elements back into the original array by iterating through the buckets in order and appending each bucket's sorted contents.

A Worked Bucket Sort Example

Here's a complete trace using the input array [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51, 0.68, 0.21, 0.12], with 10 buckets (one per element):

Step 1: Scatter each value into its bucket (bucket index = floor(10 * value)):

Step 2: Sort each non-empty bucket individually (insertion sort):

• Bucket 3 sorted: 0.32, 0.33, 0.37
• Bucket 4 sorted: 0.42, 0.47
• Bucket 5 sorted: 0.51, 0.52
• The rest were already sorted, since they held zero or one element.

Step 3: Gather the buckets back into the array, in order:

Sorted array: [0.12, 0.21, 0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52, 0.68]

Notice that bucket 3 ended up with three elements while several buckets stayed empty; this uneven distribution determines whether bucket sort runs closer to its best case or its worst case, as covered in the complexity section below.

Now that you understand how it works, you will look at the pseudocode for the bucket sort algorithm.

Boost Your Coding Skills. Nail Your Next InterviewAI-Powered Full Stack Developer ProgramExplore Program

Pseudocode and an Algorithm of the Bucket Sort Algorithm

Pseudocode of the Bucket Sort

function bucket_sort(list, B) is
    // list is the array to be sorted, B is the number of buckets
    buckets <- new array of B empty lists
    A <- the array's maximum key value

    for i = 1 to length(list) do
        Insert list[i] into buckets[floor(B * list[i] / A)]

    for i = 1 to B do
        Sort buckets[i]

    Return the concatenation of buckets[1], buckets[2], ..., buckets[B]

Let list denote the array to be sorted, and B the number of buckets used. Compute the maximum key value in linear time by iterating over all keys once. The floor function converts a floating-point index into an integer bucket index. Sort is a sorting function used to order each bucket; in most cases, insertion sort is used, but other algorithms, such as selection sort and merge sort, can also be used.

Algorithm of the Bucket Sort

bucket_Sort_Algorithm()
    Make B buckets, each covering a range of values.
    Initialize every bucket as empty.
    Place each element into the bucket matching its value.
    Sort the elements inside each bucket, then gather all buckets back into the array.
end bucket_Sort_Algorithm()

You will now learn about the complexity of the bucket sort.

Learn 45+ in-demand full-stack development skills and tools, including Frontend Development, Backend Development, Version Control and Collaboration, Database Management, and AI-Assisted Development, with our AI-Powered Full Stack Developer Course.

The Complexity of the Bucket Sort Algorithm

The Time Complexity of the Bucket Sort Algorithm

Bucket sort's time complexity largely depends on how the elements are distributed across the buckets.

Best Case Complexity: O(n + k)

• This occurs when the elements are distributed uniformly across the buckets, with roughly the same number of elements landing in each one.
• Scattering the n elements into buckets and gathering them back takes O(n). Since each bucket ends up with only a small, roughly constant number of elements, sorting all k buckets with insertion sort adds another O(k).
• Combined, that gives O(n + k), which behaves like linear time whenever k is proportional to n.

Average Case Complexity: O(n + k)

• This happens when the array's elements are distributed randomly, which for most real-world, roughly uniform data still keeps bucket sizes small.
• Bucket sort maintains this average as long as the sum of the squares of the bucket sizes stays linear in the total number of elements, which uniform or near-uniform input satisfies.

Worst Case Complexity: O(n²)

• This happens when many elements land in the same bucket, for example, when the input values cluster close together instead of spreading across the range.
• One bucket ends up holding most or all of the elements, so sorting that bucket dominates the runtime.
• If insertion sort is used on that oversized bucket, the time complexity becomes O(n²), the same as running insertion sort on the entire array. Using a faster comparison sort, such as merge sort, on the buckets caps the worst case at O(n log n), at the cost of being slower on the typical, small buckets.

The Space Complexity of the Bucket Sort Algorithm

The space complexity of bucket sort is O(n + k): O(n) to hold the elements across all buckets, and O(k) for the bucket structures themselves.

Also Read: What is Time Complexity and Space Complexity

Why Is Bucket Sort O(n + k)?

The n comes from the two full passes over the data that don't depend on how it's distributed: one pass to scatter every element into a bucket, and one pass to gather every element back out. The k comes from the overhead of maintaining k buckets, initializing them, and iterating over each one during the gather step, even the empty ones. When k stays proportional to n, and the data is close to uniformly distributed, sorting inside the buckets adds only a small constant amount of work per bucket, keeping the whole algorithm close to linear.

How Many Buckets Are Needed for Bucket Sort?

There's no fixed rule, but the standard, generic approach uses the same number of buckets as there are elements in the array (n buckets for n elements). Assuming a roughly uniform input, that keeps the expected number of elements per bucket close to 1, which is what makes the best and average cases run in close to linear time. Using far fewer buckets means each one holds more elements, pushing the runtime toward the worst case; using far more buckets than necessary wastes memory without meaningfully speeding up the sort.

Is Bucket Sort a Stable Sorting Algorithm?

Yes, bucket sort is stable, provided the sorting algorithm used inside each bucket is also stable. Since elements are only ever moved between buckets based on their value, never reordered relative to equal elements, and insertion sort (the typical choice for sorting each bucket) is itself stable, two equal elements that started in the same relative order will still be in that order after the sort completes.

Now that you understand the complexity of bucket sort, you will see some of its variants.

Get the Coding Skills You Need to SucceedAI-Powered Full Stack Developer ProgramExplore Program

Variations of Bucket Sort Algorithm

The bucket sort has the following variations:

Postman's Sort

The algorithm sorts numbers from the most significant to the least significant digit. Sorting numbers more than one digit at a time significantly increases speed.

Postman's sort is a bucket sort variant that takes advantage of a hierarchical structure of elements, typically described by a set of attributes.

Letter-sorting machines in post offices use the following algorithm: mail is first separated into domestic and international categories, then by state, province, or territory, then by the destination post office, then by routes, and so on.

Histogram Sort

A histogram is a rough representation of the numerical data distribution. Karl Pearson first used it. The first step in creating a histogram is to "bin" (or "bucket") the range of values by dividing the entire range into a series of intervals and counting how many values fall into each interval.

This variant of bucket sort, known as histogram sort or counting sort, includes a first pass that counts the number of elements placed into each bucket using a count array. Using these counts, the array values can be arranged into buckets using a series of exchanges, leaving no room for bucket storage overhead.

ProxMap Sort

ProxMap sorting takes a unique approach that is conceptually similar to hashing. This method employs a variation on hashing with buckets, but with buckets of varying sizes.

ProxMap sort works like bucket sort: it divides an array of keys into subarrays using a "map key" function that preserves a partial ordering on the keys. As each key is added to its subarray, insertion sort keeps that subarray sorted, so the entire array is sorted when ProxMap sort finishes.

Generic Bucket Sort

The most common bucket sort variant takes a list of n numeric inputs ranging from zero to some maximum value M, and divides the value range into n buckets of size M/n each. If each bucket is sorted using insertion sort, the sort can be shown to take expected linear time.

Building on your understanding of bucket sort variations, you will now compare bucket sort with other sorting algorithms.

Master the Core Concepts Behind Agentic AIWith Our Trending Applied Agentic AI CourseExplore Course

Comparison of Bucket Sort Algorithm With Other Algorithms

Here are some comparisons with other sorting algorithms.

Merge Sort

The n-way merge sort algorithm, like bucket sort, begins by dividing the list into n sublists and sorting each one. However, the sublists made by merge sort have overlapping value ranges and thus cannot be recombined by simple concatenation. Instead, a merge algorithm must interleave them.

Counting Sort

Bucket sort generalizes counting sort; in fact, bucket sort degenerates to counting sort if each bucket has size 1. Bucket sort's variable bucket size allows it to use O(n) memory rather than O(m) memory, where m is the number of different values; in exchange, it forgoes counting sort's O(n + m) worst-case behavior.

Radix Sort

Top-down radix sort is a subset of bucket sort in which both the value range and the number of buckets are limited to powers of two. As a result, each bucket is also a power of two, and the procedure can be repeated. This method can shorten the scatter phase because we only need to examine each element's bit representation prefix to determine its bucket.

Quick Sort

Bucket sort with two buckets is essentially a quicksort variant in which the pivot value is always chosen as the median of the value range. While this method works well for uniformly distributed inputs, other pivot-selection strategies in quicksort, such as randomly chosen pivots, make the input distribution more resistant to clustering.

In the next section of this tutorial, you will see the advantages, limitations, and applications of bucket sort.

Advantages, Limitations, and Applications of Bucket Sort

Advantages

• Runs in near-linear time, O(n + k), when the input is uniformly distributed across the value range.
• Since elements are assigned to buckets directly by value, rather than through comparisons, it can outperform comparison-based sorts like quicksort or merge sort on the right kind of data.
• It's stable, provided you use a stable sort within each bucket.

Limitations

• Performance depends heavily on the input's distribution. Clustered or skewed data pushes it toward its O(n²) worst case.
• It needs extra memory for the buckets, O(n + k) on top of the input array, which is more auxiliary space than an in-place comparison sort needs.
• It works best when you already know, or can reasonably estimate, the range the values fall into; an unknown or highly skewed range makes it hard to size the buckets well.

When to Use Bucket Sort

• The input is known (or reasonably assumed) to be uniformly distributed across a fixed range, such as floating-point values between 0 and 1.
• You're sorting a large volume of data where the O(n + k) average case offers a real advantage over an O(n log n) comparison sort.
• A classic real-world example is sorting mail by postal code range, or bucketing measurement data (like exam scores or sensor readings) that naturally spreads across a known interval.

Today's software teams use AI to accelerate development, automate repetitive tasks, and build smarter applications. Simplilearn's AI Accelerator Program helps you apply these capabilities through hands-on training in AI applications, intelligent agents, and workflow automation using industry-leading AI tools.

Code Implementation of Bucket Sort Algorithm

Each implementation below follows the same four steps: create n buckets, scatter each value into floor(n * value), sort each bucket with insertion sort, then gather the buckets back into the array in order. All four have been compiled and run against the same input to confirm they produce identical, correct output.

Bucket Sort in C

#include <stdio.h>

#define MAX_BUCKET_SIZE 20

// A simple insertion sort used to sort the elements inside a single bucket
void insertionSort(float bucket[], int size) {
    for (int i = 1; i < size; i++) {
        float key = bucket[i];
        int j = i - 1;
        while (j >= 0 && bucket[j] > key) {
            bucket[j + 1] = bucket[j];
            j--;
        }
        bucket[j + 1] = key;
    }
}

// arr must contain values in the range [0, 1) for this scaling approach to work.
// Returns 0 on success, -1 if a bucket overflowed (input too skewed for MAX_BUCKET_SIZE).
int bucketSort(float arr[], int n) {
    // 1. Create n empty buckets
    float buckets[n][MAX_BUCKET_SIZE];
    int bucketCount[n];
    for (int i = 0; i < n; i++) {
        bucketCount[i] = 0;
    }

    // 2. Scatter: place each element into its bucket based on its value
    for (int i = 0; i < n; i++) {
        int bucketIndex = (int)(n * arr[i]);
        if (bucketCount[bucketIndex] >= MAX_BUCKET_SIZE) {
            fprintf(stderr, "Bucket %d overflowed: more than %d elements clustered into one bucket.\n",
                    bucketIndex, MAX_BUCKET_SIZE);
            return -1;
        }
        buckets[bucketIndex][bucketCount[bucketIndex]] = arr[i];
        bucketCount[bucketIndex]++;
    }

    // 3. Sort each non-empty bucket
    for (int i = 0; i < n; i++) {
        insertionSort(buckets[i], bucketCount[i]);
    }

    // 4. Gather: concatenate all buckets back into arr, in order
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < bucketCount[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }
    return 0;
}

int main() {
    float arr[] = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51, 0.68, 0.21, 0.12};
    int n = sizeof(arr) / sizeof(arr[0]);

    if (bucketSort(arr, n) != 0) {
        return 1;
    }

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%.2f ", arr[i]);
    }
    printf("\n");
    return 0;
}

Output:

Sorted array: 0.12 0.21 0.32 0.33 0.37 0.42 0.47 0.51 0.52 0.68

Bucket Sort in C++

#include <iostream>
#include <vector>
using namespace std;

// A simple insertion sort used to sort the elements inside a single bucket
void insertionSort(vector<float>& bucket) {
    for (int i = 1; i < (int)bucket.size(); i++) {
        float key = bucket[i];
        int j = i - 1;
        while (j >= 0 && bucket[j] > key) {
            bucket[j + 1] = bucket[j];
            j--;
        }
        bucket[j + 1] = key;
    }
}

// arr must contain values in the range [0, 1) for this scaling approach to work
void bucketSort(vector<float>& arr) {
    int n = arr.size();

    // 1. Create n empty buckets
    vector<vector<float>> buckets(n);

    // 2. Scatter: place each element into its bucket based on its value
    for (int i = 0; i < n; i++) {
        int bucketIndex = n * arr[i];
        buckets[bucketIndex].push_back(arr[i]);
    }

    // 3. Sort each non-empty bucket
    for (int i = 0; i < n; i++) {
        insertionSort(buckets[i]);
    }

    // 4. Gather: concatenate all buckets back into arr, in order
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (float val : buckets[i]) {
            arr[index++] = val;
        }
    }
}

int main() {
    vector<float> arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51, 0.68, 0.21, 0.12};

    bucketSort(arr);

    cout << "Sorted array: ";
    for (float val : arr) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

Output:

Sorted array: 0.12 0.21 0.32 0.33 0.37 0.42 0.47 0.51 0.52 0.68

Dive Deep Into Java Core ConceptsJava Certification TrainingENROLL NOW

Bucket Sort in Java

import java.util.ArrayList;
import java.util.List;

public class BucketSort {

    // A simple insertion sort used to sort the elements inside a single bucket
    static void insertionSort(List<Float> bucket) {
        for (int i = 1; i < bucket.size(); i++) {
            float key = bucket.get(i);
            int j = i - 1;
            while (j >= 0 && bucket.get(j) > key) {
                bucket.set(j + 1, bucket.get(j));
                j--;
            }
            bucket.set(j + 1, key);
        }
    }

    // arr must contain values in the range [0, 1) for this scaling approach to work
    static void bucketSort(float[] arr) {
        int n = arr.length;

        // 1. Create n empty buckets
        List<List<Float>> buckets = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            buckets.add(new ArrayList<>());
        }

        // 2. Scatter: place each element into its bucket based on its value
        for (float value : arr) {
            int bucketIndex = (int) (n * value);
            buckets.get(bucketIndex).add(value);
        }

        // 3. Sort each non-empty bucket
        for (List<Float> bucket : buckets) {
            insertionSort(bucket);
        }

        // 4. Gather: concatenate all buckets back into arr, in order
        int index = 0;
        for (List<Float> bucket : buckets) {
            for (float value : bucket) {
                arr[index++] = value;
            }
        }
    }

    public static void main(String[] args) {
        float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f, 0.47f, 0.51f, 0.68f, 0.21f, 0.12f};

        bucketSort(arr);

        System.out.print("Sorted array: ");
        for (float value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Output:

Sorted array: 0.12 0.21 0.32 0.33 0.37 0.42 0.47 0.51 0.52 0.68

Bucket Sort in Python

def insertion_sort(bucket):
    """A simple insertion sort used to sort the elements inside a single bucket."""
    for i in range(1, len(bucket)):
        key = bucket[i]
        j = i - 1
        while j >= 0 and bucket[j] > key:
            bucket[j + 1] = bucket[j]
            j -= 1
        bucket[j + 1] = key


def bucket_sort(arr):
    """arr must contain values in the range [0, 1) for this scaling approach to work."""
    n = len(arr)

    # 1. Create n empty buckets
    buckets = [[] for _ in range(n)]

    # 2. Scatter: place each element into its bucket based on its value
    for value in arr:
        bucket_index = int(n * value)
        buckets[bucket_index].append(value)

    # 3. Sort each non-empty bucket
    for bucket in buckets:
        insertion_sort(bucket)

    # 4. Gather: concatenate all buckets back into arr, in order
    index = 0
    for bucket in buckets:
        for value in bucket:
            arr[index] = value
            index += 1


arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51, 0.68, 0.21, 0.12]
bucket_sort(arr)
print("Sorted array:", arr)

Output:

Sorted array: [0.12, 0.21, 0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52, 0.68]

The step-by-step Software Engineer Roadmap is designed for professionals seeking to understand the full scope of the profession. Explore the skills, tools, salary potential, and career roadmap needed to build a successful career as a software engineer.

Conclusion

Your next topic will be the bubble sort algorithm, which you will go over in great detail.

If you're looking for comprehensive, work-ready training, Simplilearn's AI-Powered Full Stack Developer Course helps you master front-end and back-end development, databases, APIs, cloud deployment, and AI-assisted development through hands-on projects and industry-relevant technologies.

As AI becomes an integral part of modern software engineering, developers are increasingly expected to build intelligent applications, agentic AI systems, and automated workflows. Simplilearn's Applied Agentic AI program helps you develop these capabilities through 10 weeks of live, hands-on learning.

Key Takeaways

• Bucket sort scatters elements into buckets by value, sorts each bucket individually, then gathers them back in order; it's more of a framework built around another sort than a single standalone algorithm.
• Time complexity ranges from O(n + k) in the best and average cases (uniform distribution) to O(n²) in the worst case (elements clustered into one bucket).
• Space complexity is O(n + k), so bucket sort is not an in-place algorithm as long as the sort used inside each bucket, typically insertion sort, is also stable.
• All code samples in this guide were compiled and run in C, C++, Java, and Python to confirm they produce the same, correct output.

FAQs

1. Is bucket sort an in-place sorting algorithm?

No. It needs extra memory for the buckets themselves, giving it O(n + k) space complexity. In-place sorts like quicksort or heapsort use only constant extra memory; bucket sort trades that for near-linear average speed.

2. Can bucket sort be used with negative numbers or values outside the [0, 1) range?

Not directly. The standard formula, floor(n * value), assumes values between 0 and 1. For other ranges, normalize the data first, for example by subtracting the minimum value from every element, so it maps into a known, non-negative interval.

3. Is bucket sort a comparison-based sorting algorithm?

Only partially. The scatter step maps values directly to bucket indexes without comparisons, which is how bucket sort beats the O(n log n) limit for pure comparison sorts. Sorting within each bucket, typically with insertion sort, is comparison-based, so the algorithm as a whole is not.

4. Can bucket sort be parallelized?

Yes. Once elements are scattered into buckets, each bucket is independent of the others, so they can be sorted in parallel across multiple threads or processors, with coordination needed only at the final gather step.

5. How do you choose the sorting algorithm used inside each bucket?

Insertion sort is standard, since it handles the small, nearly sorted lists that well-distributed buckets produce with minimal overhead. If buckets end up uneven in size, a faster sort like merge sort on the larger ones can stop one oversized bucket from dragging the whole sort toward O(n²).