Bucket Sort from Scratch (2026)
Bucket Sort is a distribution-based sorting algorithm that divides elements into several buckets, sorts each bucket individually (often using Insertion Sort or a recursive Bucket Sort), and then concatenates the buckets in order. It performs well when input is uniformly distributed across a known range.
The average time complexity is O(n + k) where n is the number of elements and k is the number of buckets. In the worst case — when all elements fall into the same bucket — it degrades to O(n²). Bucket Sort is widely used for sorting floating-point numbers in the range [0, 1).
Algorithm and Implementation
First, create k empty buckets. Then iterate through the array and place each element into its corresponding bucket based on a mapping function (e.g., floor(value × k)). Sort each non-empty bucket individually, typically with Insertion Sort since buckets contain few elements. Finally, concatenate all buckets in order.
void bucketSort(float arr[], int n) {
vector buckets[n];
for (int i = 0; i < n; i++) {
int idx = n * arr[i];
buckets[idx].push_back(arr[i]);
}
for (int i = 0; i < n; i++)
sort(buckets[i].begin(), buckets[i].end());
int idx = 0;
for (int i = 0; i < n; i++)
for (float v : buckets[i])
arr[idx++] = v;
} Choosing Bucket Count
The number of buckets is typically set to n (the array size). More buckets reduce per-bucket size but increase overhead. A common heuristic is k = √n. The mapping function must distribute elements uniformly; for [0, 1) floats, floor(value × k) works well.
# Python: Bucket Sort
import math
def bucket_sort(arr):
n = len(arr)
buckets = [[] for _ in range(n)]
for v in arr:
buckets[int(v * n)].append(v)
for b in buckets:
b.sort()
return [v for b in buckets for v in b]Frequently Asked Questions
When should I use Bucket Sort?
Use Bucket Sort when input is uniformly distributed over a known range, especially for floating-point numbers in [0, 1). It works poorly with highly skewed data.
Is Bucket Sort stable?
Bucket Sort is stable if the sorting algorithm used within buckets is stable. Insertion Sort and Merge Sort are stable choices for the per-bucket step.
Originally published on Ayodhyyya. Last updated June 1, 2026.