Offensive Security Researcher & Quantum Cryptography Analyst

Bucket Sort Algorithm: A Linear-Time Distribution Sorting Technique

Abdul Wahab Junaid
Bucket Sort: A Linear-Time Distribution Sorting Algorithm

When I study sorting algorithms, I usually start with comparison-based methods like quicksort or mergesort, which are bound by the $O(n \log n)$ comparison lower bound. Bucket sort interests me because it steps outside that model entirely — instead of comparing elements against each other, I distribute elements into groups (buckets) based on their value, and then sort within each group. Under the right assumptions about my input data, this lets me sort in linear time, which is faster than any comparison-based algorithm can achieve. I find this topic important because it teaches me that the $O(n \log n)$ barrier is not a universal law — it only applies when I restrict myself to comparisons. Bucket sort, along with counting sort and radix sort, shows me how to break that barrier when I know something extra about the structure of my data.

History and Background

I understand bucket sort as part of a family of distribution sorting algorithms that emerged alongside counting sort and radix sort in the early development of computer science, with roots going back to punch-card sorting machines used for tabulating data in the early-to-mid 20th century. The algorithm’s modern formalization as a comparison-free, linear-expected-time technique is presented in detail in Introduction to Algorithms (CLRS), where it’s introduced as a natural extension of counting sort — instead of one bucket per discrete value, I use ranges of values, which lets me handle real-valued, continuously distributed data. The core idea of “divide the range into buckets, sort each bucket, concatenate” long predates its formal name and appears in various forms across data processing history, particularly in hardware and card-sorting systems that physically routed items into bins.

Problem Statement

I want to sort an array of n elements, ideally in less than $O(n \log n)$ time. Comparison-based sorts cannot do this in the worst case, so I need an approach that avoids relying solely on pairwise comparisons. My constraint is that this only works well when I can make a reasonable assumption about my input — specifically, that the values are uniformly distributed over a known range. If that assumption holds, I want an algorithm that achieves expected linear time, $O(n)$, by exploiting the structure of the distribution rather than comparing every pair of elements.

Core Concepts

How It Works

  1. I determine the range of my input values (minimum and maximum), or I assume a known range such as [0, 1) for normalized data.
  2. I decide how many buckets to create — typically n buckets for n input elements, to keep the expected number of elements per bucket close to 1.
  3. I compute, for each element, which bucket it belongs to using a mapping function, usually of the form: bucket_index = floor(n * value) for data in [0, 1), or a scaled version for other ranges.
  4. I insert each element into its assigned bucket, preserving the original order if I want stability.
  5. I sort each individual bucket using an efficient algorithm for small lists — insertion sort is the conventional choice because buckets are expected to be small.
  6. I concatenate all buckets in order, from the bucket holding the smallest range to the one holding the largest, producing the final sorted array.

Working Principle

The internal logic of bucket sort relies on turning the sorting problem into two smaller, cheaper problems. First, I use the mapping function to perform a “coarse sort” — this places every element roughly near its correct final position without any comparisons at all, just arithmetic. Second, I clean up the “local disorder” within each bucket using a comparison-based sort, but because each bucket is expected to hold only a small, near-constant number of elements (thanks to the uniform distribution assumption), this cleanup step is cheap — close to constant time per bucket on average. The combination of a fast coarse placement and cheap local correction is what allows the overall algorithm to achieve expected linear time, even though the local sorting step is technically $O(k \log k)$ or $O(k^2)$ per bucket of size k.

Mathematical Foundation

I model the expected time complexity using probability theory. Suppose I have n elements uniformly distributed over [0, 1), divided into n buckets. I let $n_i$ denote the number of elements that land in bucket i. The total running time is:

$$ T(n) = \Theta(n) + \sum_{i=0}^{n-1} O(n_i^2) $$

The $\Theta(n)$ term covers the scatter and gather phases, and the summation covers the cost of sorting each bucket with insertion sort, which costs $O(n_i^2)$ in the worst case for a bucket of size $n_i$.

Taking the expectation over the randomness of a uniform distribution, I compute:

$$ E[T(n)] = \Theta(n) + \sum_{i=0}^{n-1} O(E[n_i^2]) $$

Since each element independently lands in a given bucket with probability $1/n$, the count $n_i$ follows a binomial distribution, $n_i \sim \text{Binomial}(n, 1/n)$. I know that for a binomial random variable:

$$ E[n_i^2] = \text{Var}(n_i) + (E[n_i])^2 = n \cdot \frac{1}{n}\left(1 – \frac{1}{n}\right) + \left(\frac{n}{n}\right)^2 = \left(1 – \frac{1}{n}\right) + 1 = 2 – \frac{1}{n} $$

Substituting this back:

$$ E[T(n)] = \Theta(n) + \sum_{i=0}^{n-1} O\left(2 – \frac{1}{n}\right) = \Theta(n) + n \cdot O(1) = \Theta(n) $$

This confirms that, under the uniform distribution assumption, I achieve expected linear time, $\Theta(n)$, even though the worst-case time (when all elements land in a single bucket) degrades to $O(n^2)$.

Diagrams

flowchart TD
    A[Start: unsorted array of n elements in known range] --> B[Create n empty buckets]
    B --> C[For each element, compute its bucket index]
    C --> D[Insert element into corresponding bucket]
    D --> E{All elements scattered?}
    E -- No --> C
    E -- Yes --> F[Sort each bucket individually using insertion sort]
    F --> G[Concatenate buckets in order]
    G --> H[Return sorted array]

Pseudocode

ALGORITHM BucketSort(A, n)
    // A is an array of n elements with values in the range [0, 1)
    create array of n empty buckets B[0..n-1]

    for i = 0 to n - 1:
        index = floor(n * A[i])
        insert A[i] into B[index]

    for i = 0 to n - 1:
        InsertionSort(B[i])

    result = empty list
    for i = 0 to n - 1:
        append all elements of B[i] to result

    return result

Step-by-Step Example

I sort the array A = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68], which has n = 10 elements, all in the range [0, 1).

  1. I create 10 empty buckets, indexed 0 through 9.
  2. I compute the bucket index for each element using floor(10 * value):
    • 0.78 → bucket 7
    • 0.17 → bucket 1
    • 0.39 → bucket 3
    • 0.26 → bucket 2
    • 0.72 → bucket 7
    • 0.94 → bucket 9
    • 0.21 → bucket 2
    • 0.12 → bucket 1
    • 0.23 → bucket 2
    • 0.68 → bucket 6
  3. My buckets now look like:
    • Bucket 1: [0.17, 0.12]
    • Bucket 2: [0.26, 0.21, 0.23]
    • Bucket 3: [0.39]
    • Bucket 6: [0.68]
    • Bucket 7: [0.78, 0.72]
    • Bucket 9: [0.94]
  4. I sort each non-empty bucket individually:
    • Bucket 1: [0.12, 0.17]
    • Bucket 2: [0.21, 0.23, 0.26]
    • Bucket 3: [0.39]
    • Bucket 6: [0.68]
    • Bucket 7: [0.72, 0.78]
    • Bucket 9: [0.94]
  5. I concatenate all buckets in order, producing:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

Time Complexity

I note that this worst case is a direct consequence of violating my core assumption; if I know my data will not be uniformly distributed, I should not use plain bucket sort without modification.

Space Complexity

I need auxiliary space for n buckets, which in the worst case (all elements in one bucket) still totals $O(n)$ extra space across all buckets combined, since I’m redistributing the same n elements. I typically implement buckets as dynamic lists (linked lists or resizable arrays), so the overhead is $O(n)$ for bucket structures plus $O(n)$ for the elements themselves, giving me overall $O(n)$ space complexity. This is not an in-place algorithm.

Correctness Analysis

I establish correctness in two parts. First, I confirm that my bucket-mapping function is order-preserving across buckets — meaning that any element in bucket i is guaranteed to be less than or equal to any element in bucket i+1, because bucket boundaries are defined by contiguous, non-overlapping value ranges. Second, I confirm that the insertion sort applied within each bucket correctly sorts the elements within that bucket, which is a well-established, previously proven result for insertion sort. Since (a) buckets are internally sorted and (b) buckets themselves are in increasing order relative to each other, concatenating them in bucket order produces a fully sorted array. This argument holds regardless of the input distribution — correctness does not depend on uniformity, only efficiency does.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

#define N 10  /* number of elements and number of buckets */

/* A simple node structure for a bucket implemented as a linked list */
typedef struct Node {
    float value;
    struct Node *next;
} Node;

/* Inserts a value into a bucket's linked list, keeping the list sorted (insertion sort as I go) */
void insertSorted(Node **head, float value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = NULL;

    if (*head == NULL || (*head)->value >= value) {
        newNode->next = *head;
        *head = newNode;
        return;
    }

    Node *current = *head;
    while (current->next != NULL && current->next->value < value) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
}

/* Performs bucket sort on an array of floats in the range [0, 1) */
void bucketSort(float arr[], int n) {
    Node *buckets[N] = {NULL}; /* initialize all bucket heads to NULL */
    int i;

    /* Scatter phase: place each element into its bucket, sorted on insertion */
    for (i = 0; i < n; i++) {
        int bucketIndex = (int)(N * arr[i]);
        insertSorted(&buckets[bucketIndex], arr[i]);
    }

    /* Gather phase: concatenate all buckets back into the original array */
    int index = 0;
    for (i = 0; i < N; i++) {
        Node *current = buckets[i];
        while (current != NULL) {
            arr[index++] = current->value;
            Node *temp = current;
            current = current->next;
            free(temp); /* free memory as I go to avoid leaks */
        }
    }
}

int main(void) {
    float arr[N] = {0.78f, 0.17f, 0.39f, 0.26f, 0.72f, 0.94f, 0.21f, 0.12f, 0.23f, 0.68f};
    int i;

    bucketSort(arr, N);

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

    return 0;
}

Sample Input and Output

Input:

Array: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

Output:

Sorted array: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version