How to pick the number of buckets?

The number of buckets should ideally be equal to the number of elements (n) or based on the input distribution to ensure balanced buckets.

What is the time complexity of Bucket Sort?

On average, it is O(n + k) with a uniform distribution. In the worst case (all elements in one bucket), it degrades to the complexity of the underlying sort (usually O(n²)).

Is Bucket Sort stable?

Yes, if the underlying sorting algorithm used for the buckets is also stable.

Bucket Sort

Bucket sort is a distribution sort that scatters elements into buckets, sorts each bucket individually, and then gathers them.

Intuition

Imagine sorting a stack of exam papers scored 0.0 to 1.0 (percentages). You wouldn't compare every paper to every other paper. Instead, you'd quickly put all papers with 80s scores in one folder, 90s in another, etc. Since each folder ends up with only a few papers, sorting each small folder is very fast. Finally, you just stack the folders in order: 0s, 10s... 90s.

Concept

Bucket sort spreads the values across n buckets by where they fall in the range, sorts each bucket on its own (usually with insertion sort), then reads the buckets back in order. It is fast when values are spread evenly, because every bucket stays small; when they pile into one bucket, the whole job becomes sorting that one bucket.

How it Works

Algorithm:

Create Buckets: Initialize n empty buckets.
Scatter: Go through the original array. For each element, determine its bucket index (e.g., n * value) and insert it.
Sort Buckets: Sort each non-empty bucket (typically using Insertion Sort).
Gather: Visit the buckets in order and put all elements back into the original array.

Step-by-Step Breakdown

Watch the visualization:

Scatter Phase: Elements move from the main array into their respective 'buckets' below.
Sorting Phase: Each bucket is sorted internally (shown by color change).
Gather Phase: Elements are moved back from buckets to the main array in sorted order.

When to Use

Uniform Distribution: When input is uniformly distributed over a range (e.g., [0, 1)).
Floating Point Numbers: Excellent for sorting floats where Counting Sort is inapplicable.

When NOT to Use

Clustered Data: If many elements fall into the same bucket, performance degrades to O(n²).
Limited Memory: Requires extra space for the buckets.

How to Identify

Look for problems involving floating point numbers or requirements for O(n) time complexity where comparison-based sorting (O(n log n)) is too slow, and data is bounded.

Sample Problems

Maximum Gap (LeetCode 164)

Specifically designed to be solved using the Bucket/Pigeonhole principle.

Top K Frequent Elements (LeetCode 347)

Can be solved using a variant of bucket sort (grouping by frequency).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Radix Sort

Linear Search