ZetCode

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.

PropertyValue
Average timeO(n + k) for uniformly distributed data, k buckets
Worst case timeO(n2) with insertion sort, when all elements fall into one bucket
Extra spaceO(n + k)
Stableyes, 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.

bucket_sort.py
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.

bucket_trace.py
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.

bucket_range.py
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.

distribution.py
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.

quantile_buckets.py
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.

bucket_words.py
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.

bucket_records.py
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.

benchmark.py
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

bisect – 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

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.