Python bucket sort
last modified November 18, 2026 Python 3.15
In this article we explain the bucket sort algorithm in Python. We implement and trace it, extend it to arbitrary ranges, examine how the distribution of the data affects it, and use it for words and records.
Bucket sort, also called bin sort, is a distribution sort. It does not compare all elements with each other. Instead, it uses the value of each element to decide which bucket it belongs to. It works best when the values are spread evenly over a known range, for example random floats between 0 and 1.
Bucket sort algorithm
Bucket sort divides the range of the values into equally wide intervals, the buckets. It distributes the elements into the buckets, sorts each bucket with another algorithm, usually insertion sort, and concatenates the buckets in order. Since the buckets cover consecutive intervals, every element of a bucket is smaller than every element of the next bucket.
| Property | Value |
|---|---|
| Average time | O(n + k) for uniformly distributed data, k buckets |
| Worst case time | O(n2) with insertion sort, when all elements fall into one bucket |
| Extra space | O(n + k) |
| Stable | yes, if the bucket sort is stable |
Bucket sort example
The following example sorts floats from the interval [0, 1) using
n buckets for n elements.
def insertion_sort(vals):
for i in range(1, len(vals)):
item = vals[i]
j = i - 1
while j >= 0 and vals[j] > item:
vals[j + 1] = vals[j]
j -= 1
vals[j + 1] = item
def bucket_sort(vals):
n = len(vals)
buckets = [[] for _ in range(n)]
for v in vals:
buckets[int(v * n)].append(v)
for bucket in buckets:
insertion_sort(bucket)
return [v for bucket in buckets for v in bucket]
nums = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
print(bucket_sort(nums))
A value v goes to the bucket with index
int(v * n); with ten values, 0.78 goes to bucket 7. Each bucket
is sorted with insertion sort, which is fast for the few elements a bucket
usually holds. The comprehension concatenates the buckets.
$ python bucket_sort.py [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
Tracing the buckets
We print the interval of each bucket, its content, and its content after sorting.
nums = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
n = len(nums)
buckets = [[] for _ in range(n)]
for v in nums:
buckets[int(v * n)].append(v)
for i, bucket in enumerate(buckets):
print(f'bucket {i} [{i / n:.1f}, {(i + 1) / n:.1f}): '
f'{bucket} -> {sorted(bucket)}')
With uniformly distributed data, most buckets hold zero, one, or two elements. Five buckets are empty here and the largest one has three elements, so the sorting step does very little work.
$ python bucket_trace.py bucket 0 [0.0, 0.1): [] -> [] bucket 1 [0.1, 0.2): [0.17, 0.12] -> [0.12, 0.17] bucket 2 [0.2, 0.3): [0.26, 0.21, 0.23] -> [0.21, 0.23, 0.26] bucket 3 [0.3, 0.4): [0.39] -> [0.39] bucket 4 [0.4, 0.5): [] -> [] bucket 5 [0.5, 0.6): [] -> [] bucket 6 [0.6, 0.7): [0.68] -> [0.68] bucket 7 [0.7, 0.8): [0.78, 0.72] -> [0.72, 0.78] bucket 8 [0.8, 0.9): [] -> [] bucket 9 [0.9, 1.0): [0.94] -> [0.94]
Values from any range
For values outside [0, 1), we compute the bucket from the minimum and the maximum of the data.
def bucket_sort(vals, count=None):
if len(vals) <= 1:
return list(vals)
count = count or len(vals)
lo, hi = min(vals), max(vals)
if lo == hi:
return list(vals)
width = (hi - lo) / count
buckets = [[] for _ in range(count)]
for v in vals:
i = min(int((v - lo) / width), count - 1)
buckets[i].append(v)
return [v for bucket in buckets for v in sorted(bucket)]
prices = [19.99, 5.49, 102.0, 45.5, 7.25, 89.9, 33.0, 64.75, 12.0, 99.99]
print(bucket_sort(prices))
ages = [34, 7, 81, 23, 45, 19, 62, 7, 55, 90, 28]
print(bucket_sort(ages, count=4))
Each bucket is (hi - lo) / count wide. The maximum would get
the index count, one past the last bucket, so
min clamps it. If all values are equal, the width would be
zero, so we return a copy right away. The buckets are sorted with
sorted; the optional count parameter sets the
number of buckets, here four buckets for the ages.
$ python bucket_range.py [5.49, 7.25, 12.0, 19.99, 33.0, 45.5, 64.75, 89.9, 99.99, 102.0] [7, 7, 19, 23, 28, 34, 45, 55, 62, 81, 90]
The data distribution matters
Bucket sort assumes that the values are spread evenly. We compare the bucket sizes for a uniform, a normal, and a skewed (Pareto) distribution.
import random
def bucket_sizes(vals, count):
lo, hi = min(vals), max(vals)
width = (hi - lo) / count
sizes = [0] * count
for v in vals:
sizes[min(int((v - lo) / width), count - 1)] += 1
return sizes
rng = random.Random(17)
n = 10_000
uniform = [rng.random() for _ in range(n)]
normal = [rng.gauss(0, 1) for _ in range(n)]
skewed = [rng.paretovariate(1.5) for _ in range(n)]
for name, data in [('uniform', uniform), ('normal', normal), ('skewed', skewed)]:
sizes = bucket_sizes(data, 10)
work = sum(s * s for s in sizes)
print(f'{name:<8} {sizes} sum of squares {work:,}')
We distribute 10,000 values into ten equally wide buckets. Insertion sort on a bucket of size s takes about s2 steps, so the sum of squares estimates the work. The uniform data fills the buckets evenly. The normal data piles up in the middle buckets and doubles the work. In the skewed data, a few very large values stretch the range, and almost all values end up in the first bucket; bucket sort degrades to plain insertion sort.
$ python distribution.py uniform [967, 1009, 1026, 1009, 1021, 1003, 1004, 1019, 966, 976] sum of squares 10,004,486 normal [2, 54, 311, 1280, 2624, 2993, 1905, 669, 146, 16] sum of squares 21,679,624 skewed [9951, 31, 11, 1, 3, 0, 1, 0, 1, 1] sum of squares 99,023,496
Buckets from sample quantiles
For data with an unknown or skewed distribution, we can choose the bucket boundaries from a sorted random sample instead of splitting the range evenly. This is the idea behind sample sort.
import bisect
import random
def bucket_sort(vals, count, sample_size=200, seed=0):
rng = random.Random(seed)
sample = sorted(rng.sample(vals, min(sample_size, len(vals))))
bounds = [sample[len(sample) * i // count] for i in range(1, count)]
buckets = [[] for _ in range(count)]
for v in vals:
buckets[bisect.bisect_right(bounds, v)].append(v)
print('bucket sizes:', [len(b) for b in buckets])
return [v for bucket in buckets for v in sorted(bucket)]
rng = random.Random(17)
skewed = [rng.paretovariate(1.5) for _ in range(10_000)]
res = bucket_sort(skewed, 10)
print(res == sorted(skewed))
We sort a sample of 200 values and take every 20th one as a bucket
boundary. The bisect_right function finds the bucket of each
value by binary search among the boundaries. The same skewed data that put
9951 values into one bucket now produces buckets of similar sizes.
$ python quantile_buckets.py bucket sizes: [1135, 750, 975, 893, 1167, 1262, 734, 1601, 743, 740] True
Sorting words
Buckets need not be numeric intervals. Here the first letter of a word selects the bucket.
def bucket_sort_words(words):
buckets = {}
for w in words:
buckets.setdefault(w[0].lower(), []).append(w)
for letter in sorted(buckets):
print(f'{letter}: {buckets[letter]}')
return [w for letter in sorted(buckets)
for w in sorted(buckets[letter], key=str.lower)]
words = ['banana', 'Apple', 'cherry', 'avocado', 'blueberry', 'Cranberry',
'apricot', 'date', 'coconut']
print(bucket_sort_words(words))
A dictionary maps lowercase first letters to buckets. We print the buckets and then concatenate them in alphabetical order, sorting each one case-insensitively. Words starting with uppercase letters land in the same bucket as their lowercase relatives.
$ python bucket_words.py a: ['Apple', 'avocado', 'apricot'] b: ['banana', 'blueberry'] c: ['cherry', 'Cranberry', 'coconut'] d: ['date'] ['Apple', 'apricot', 'avocado', 'banana', 'blueberry', 'cherry', 'coconut', 'Cranberry', 'date']
Grouping and sorting records
The distribution step alone is useful: it groups records into ranges, like a histogram.
from dataclasses import dataclass
@dataclass
class Product:
name: str
price: float
def bucket_sort(items, key, count, lo, hi):
width = (hi - lo) / count
buckets = [[] for _ in range(count)]
for item in items:
i = min(int((key(item) - lo) / width), count - 1)
buckets[i].append(item)
return buckets
products = [
Product('pen', 1.5), Product('notebook', 4.2), Product('backpack', 39.0),
Product('ruler', 1.5), Product('calculator', 18.9), Product('stapler', 7.4),
Product('marker', 2.1), Product('lamp', 24.5), Product('glue', 2.1),
]
buckets = bucket_sort(products, key=lambda p: p.price, count=4, lo=0, hi=40)
for i, bucket in enumerate(buckets):
print(f'{i * 10:>2}-{i * 10 + 10} EUR:', [p.name for p in bucket])
res = [p for b in buckets for p in sorted(b, key=lambda p: p.price)]
print([f'{p.name} {p.price}' for p in res])
We put products into four price ranges of 10 euros. The buckets already
answer questions such as which products cost less than 10 euros. Sorting
each bucket with the stable sorted gives the fully sorted list;
products with the same price keep their input order, such as the pen before
the ruler.
$ python bucket_records.py 0-10 EUR: ['pen', 'notebook', 'ruler', 'stapler', 'marker', 'glue'] 10-20 EUR: ['calculator'] 20-30 EUR: ['lamp'] 30-40 EUR: ['backpack'] ['pen 1.5', 'ruler 1.5', 'marker 2.1', 'glue 2.1', 'notebook 4.2', 'stapler 7.4', 'calculator 18.9', 'lamp 24.5', 'backpack 39.0']
Benchmark
We compare bucket sort with sorted on a million random floats,
using one million and one thousand buckets.
import random
import timeit
def bucket_sort(vals, count):
buckets = [[] for _ in range(count)]
for v in vals:
buckets[int(v * count)].append(v)
res = []
for bucket in buckets:
bucket.sort()
res.extend(bucket)
return res
rng = random.Random(18)
data = [rng.random() for _ in range(1_000_000)]
tests = [('bucket sort, 1,000,000 buckets', lambda: bucket_sort(data, len(data))),
('bucket sort, 1,000 buckets', lambda: bucket_sort(data, 1000)),
('sorted', lambda: sorted(data))]
for name, func in tests:
t = timeit.timeit(func, number=3) / 3
print(f'{name:<31} {t:.3f} s')
The buckets are sorted with the built-in list.sort. A million
buckets mean a million small lists, and creating them is expensive in
Python. With a thousand buckets of about a thousand values each, bucket
sort is as fast as sorted or even slightly faster, because the
C sort of many small lists is cheap and the distribution loop is simple. The
times vary between runs and machines.
$ python benchmark.py bucket sort, 1,000,000 buckets 0.669 s bucket sort, 1,000 buckets 0.185 s sorted 0.203 s
Source
Sorting Techniques – Python documentation
In this article we have implemented bucket sort in Python and examined how the data distribution affects it. See also Python counting sort, Python radix sort, Python insertion sort, and Python random module.
Author
List all Python tutorials.