Bucket Sort Explained
Bucket Sort distributes elements into buckets, sorts each, and concatenates them. Learn how it works, its O(n) average case, and when it is the right choice.
On this page +
Bucket Sort is a distribution sort that scatters elements into a number of buckets, sorts each bucket individually, then concatenates them. When the input is uniformly distributed, it achieves O(n) average time, making it a great fit for floating-point values spread evenly across a range.
How Bucket Sort works #
1) Create k empty buckets covering equal sub-ranges of the input. 2) Distribute each element into the bucket for its range. 3) Sort each bucket (often with Insertion Sort, since buckets are small). 4) Concatenate the buckets in order. If elements are spread evenly, each bucket holds only a few items, so the per-bucket sort is cheap.
Complexity #
Bucket Sort is O(n + k) average when data is uniform, but degrades to O(n²) if all elements land in one bucket (skewed data). It uses O(n + k) space and its stability depends on the per-bucket sort. It is most useful for normalized floating-point data such as values in [0, 1).
Bucket vs Counting vs Radix #
These three non-comparison sorts are easy to confuse. Counting Sort buckets by exact integer value; Radix Sort buckets digit by digit; Bucket Sort buckets by value range and sorts within each. Choose Bucket Sort for uniformly distributed real numbers. Try the related Counting Sort and Radix Sort guides.
Frequently asked questions
What is the time complexity of Bucket Sort? +
When is Bucket Sort a good choice? +
See it in motion
Watch this algorithm and nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.