Well-balanced buckets make distribution and collection Θ(n+k).
Sorting algorithms · 7/7
Bucket sort
Distributes by range, sorts locally and concatenates.
Average timeΘ(n + k)
SpaceΘ(n + k)
StableDepends
In placeNo
How it works
Each bucket covers an ordered interval. Sort inside each bucket and concatenate left to right.
Invariant: Every value in bucket i precedes values in later buckets; only local order remains.
Step-by-step visualization
Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.
Use 2 to 16 values. This visualizer accepts values from 0 to 999.
- Comparisons
- 0
- Writes
- 0
- Swaps
- 0
- Pass / level
- 0
active
comparison
pivot / key
final
Pseudocode linked to the visualization
create k empty bucketsfor value in Aindex ← bucketFor(value)append value to bucket[index]for each bucketsort bucketconcatenate all buckets into A
The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.
Complexity analysis
Under a uniform model with k=Θ(n), expected bucket size is constant: Θ(n+k).
If every value lands in one insertion-sorted bucket, time is Θ(n²).
The k buckets hold n total items: Θ(n+k). Stability depends on the local sort.
Properties at a glance
Stability concerns the relative order of elements with equal keys.
This classification refers to the version shown on this page.
When to use it and what to avoid
A good choice when…
Effective when a roughly uniform distribution is known.
Common mistake
Bucket boundaries are part of the algorithm; poor boundaries cause imbalance.