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
- Bucket – a container that holds all elements falling within a specific sub-range of the overall value range.
- Uniform distribution assumption – the assumption that input elements are spread roughly evenly across their range, so each bucket receives a comparable, small number of elements.
- Scatter-sort-gather – the three-phase pattern I follow: scatter elements into buckets, sort each bucket individually (often with insertion sort), then gather results back into a single sorted array.
- Stable sort – a sort where elements with equal keys retain their relative input order; bucket sort can be made stable if I preserve insertion order within buckets and use a stable sort inside each bucket.
- Distribution sort vs. comparison sort – bucket sort belongs to the distribution sort family, which uses knowledge of key values to place elements directly, rather than deriving order purely from pairwise comparisons.
How It Works
- I determine the range of my input values (minimum and maximum), or I assume a known range such as [0, 1) for normalized data.
- 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.
- 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. - I insert each element into its assigned bucket, preserving the original order if I want stability.
- 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.
- 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).
- I create 10 empty buckets, indexed 0 through 9.
- 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
- 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]
- 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]
- 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
- Best case: $O(n)$, when elements distribute evenly across buckets, so each bucket has a constant number of elements.
- Average case: $O(n)$ (expected time), assuming a uniform distribution, as I proved mathematically above.
- Worst case: $O(n^2)$, which happens when all elements land in the same bucket — for example, if my input is not uniformly distributed but heavily skewed, insertion sort on a single bucket of size n degrades to $O(n^2)$.
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
- I achieve expected linear time, $O(n)$, which beats the comparison-sort lower bound of $O(n \log n)$ when my assumptions hold.
- The algorithm is naturally stable if I preserve insertion order within buckets and use a stable sort internally.
- It parallelizes well, since scattering elements into buckets and sorting each bucket can be done independently and concurrently.
- It performs very well in practice for real-valued data that is known to be roughly uniform, such as normalized measurements or hashed keys.
Disadvantages
- Performance depends heavily on the input distribution; skewed or clustered data causes buckets to become unbalanced, degrading performance toward $O(n^2)$.
- It requires prior knowledge (or a reasonable estimate) of the value range to construct buckets effectively.
- It uses $O(n)$ extra space, so it is not suitable when memory is tightly constrained.
- It is less general-purpose than comparison sorts like quicksort or mergesort, which work correctly and efficiently on arbitrary orderable data without distributional assumptions.
Applications
- I use bucket sort to sort large sets of floating-point numbers known to be uniformly distributed, such as normalized sensor readings or probabilities.
- It’s used in histogram generation and computational geometry algorithms where data naturally falls into range-based buckets.
- Some external sorting and parallel/distributed sorting systems use bucket sort as a first-pass partitioning step, distributing data across multiple machines or disks before a local sort.
- It appears in graphics and rendering pipelines for sorting pixels, vertices, or other data with predictable value ranges.
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
- I choose the number of buckets carefully — too few buckets cause overcrowding (degrading toward $O(n^2)$), while too many buckets waste memory and overhead on mostly-empty buckets. Using n buckets for n elements is the standard balanced choice under a uniform distribution.
- I can replace insertion sort within each bucket with a different algorithm if I expect bucket sizes to sometimes be large — for example, using quicksort or even recursively applying bucket sort for skewed sub-distributions.
- I can dynamically estimate the input distribution instead of assuming uniformity, and construct non-uniform bucket boundaries (e.g., quantile-based buckets) so that each bucket receives roughly the same number of elements regardless of skew.
- I can parallelize both the scatter phase (distributing elements across threads or machines) and the per-bucket sort phase, since buckets are independent of each other once elements are assigned.
- I use arrays instead of linked lists for buckets when I can preallocate reasonable capacity, since arrays have better cache locality than linked lists.
Common Mistakes
- I sometimes forget to handle the edge case where a value equals the upper bound of the range (e.g., value = 1.0 in a [0, 1) range), which can cause an out-of-bounds bucket index; I need to clamp or explicitly check for this.
- I sometimes assume bucket sort works well on any data without checking whether the uniform distribution assumption actually holds, leading to unexpectedly poor performance on skewed data.
- I sometimes forget to free dynamically allocated bucket memory after the gather phase, causing memory leaks in C implementations.
- I sometimes use a fixed, small number of buckets regardless of n, which causes overcrowding and negates the linear-time advantage as n grows.
- I sometimes conflate bucket sort with counting sort — they are related but distinct: counting sort uses one bucket per discrete value, while bucket sort uses buckets that span ranges of continuous values.
Further Reading
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (CLRS), MIT Press — https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, “Bucket Sort” — https://www.geeksforgeeks.org/dsa/bucket-sort-2/
- Wikipedia, “Bucket sort” — https://en.wikipedia.org/wiki/Bucket_sort
- Sedgewick and Wayne, Algorithms, 4th Edition, Addison-Wesley — https://algs4.cs.princeton.edu/home/
- MIT OpenCourseWare, Introduction to Algorithms (6.006/6.046) lecture notes — https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/
