Sorting Algorithm

Bucket Sort

Scatters elements into a number of buckets based on their value range, sorts each (small) bucket individually, then concatenates the buckets in order. When values are spread evenly across the range, each bucket ends up tiny — sorting them is nearly free, so the whole thing runs close to O(n).

BestO(n + k)
AverageO(n + k)
WorstO(n²)
SpaceO(n + k)
StableYes

Try It — Animated Flow

29
8
44
15
3
37
21
Bucket sort scatters values into 5 buckets by range, sorts each bucket, then concatenates them in order.
Step 1 / 10
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Uniformly distributed floats
The textbook use case: sorting numbers spread evenly across [0, 1), like normalized scores or probabilities — every bucket ends up with roughly one element.
Image processing / binning
Grouping pixels by brightness or color range into 'buckets' before further processing is a direct real-world instance of this idea.
Distributed / parallel sorting
Splitting a huge dataset by value range across multiple machines (each sorts its own range) is bucket sort scaled out to a cluster.
Grading on a curve
Sorting students into letter-grade ranges (A/B/C/D/F) before ranking within each grade is a natural bucket-sort-shaped problem.

Trade-offs

Reach for it when
  • Data is roughly uniformly distributed over a known range
  • You can afford O(n) extra space for the buckets
  • You want near-linear performance on well-behaved input
Avoid it when
  • Data is heavily skewed (everything lands in one bucket → O(n²))
  • The value range isn't known ahead of time
  • Memory for buckets isn't available