Bucket Sort
A distribution sort that scatters elements into buckets, sorts them individually, and then gathers them.
Buckets (Normalized Range)
Ready to sort
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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 works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm (often Insertion Sort) or by recursively applying the bucket sorting algorithm.
How it Works
Algorithm:
- Create Buckets: Initialize
nempty 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.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.