Bucket Sort Visualization

Bucket Sort spreads values into buckets by range, sorts each bucket, then joins them.

How it works

Bucket Sort divides the range of values into equal-width buckets, drops each value into its bucket, sorts each bucket (here with Insertion Sort), then concatenates the buckets in order. This version uses about √n buckets.

When values are spread evenly, every bucket is small and the total work is close to linear. When values bunch up in a few buckets, those buckets get large and it slows toward Insertion Sort's n². It needs extra memory for the buckets and is stable when the inner sort is stable.

What to watch for

Watch the values gather into coloured blocks first, then each block sorts itself.

Complexity

Best

n + k

Average

n + k

Worst

n²

Extra space

n + k

Stable

Yes

Race it

Same shuffle, same speed, one winner: Bucket vs Quick. Or open the studio to try other layouts, sizes and speeds, and make a video of it.

FAQ