Bucket Sort
Scatter values into equal value ranges, sort each small bucket, gather in order: linear on even data.
42 x 4 / 100 = 1, so 42 goes into bucket 25-49 as its first value.
What you will see
Values fly into buckets by range; each bucket sorts; buckets concatenate.
Cost
| Best | O(n + k) |
|---|---|
| Average | O(n + k) |
| Worst | O(n^2) |
| Space | O(n + k) |
Worst case when all values land in one bucket; stability depends on the inner sort.
Properties
- × comparison based
- ✓ stable
- × in place
- × adaptive
- × online
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, compare two runs.
Screen readers: Cells announce index, value and state (comparing, swapped, sorted); each step announces the comparison outcome and any move.
Reduced motion: Swaps become value crossfades with outline flashes; sorted-region growth is a static span change.
Before this
Related
Taught by the same lesson
More Sorts covers these too, in the same run.