Bucket Sort
SortingMediumDistribute elements into range-mapped buckets, sort them, and gather them.
Alt+Shift+B
Configuration Panel
Buckets Distribution & Concatenation Visualizer
230
81
562
123
384
55
726
167
Step: 1 / 1
Time Complexity
O(N + B) average (for uniform distribution), O(N^2) worst case
Space Complexity
O(N + B) auxiliary buckets memory
Conceptual Overview
Bucket Sort distributes elements of an array into multiple 'buckets'. Each bucket is then sorted individually, either recursively or using a different sorting algorithm, and then concatenated.
Algorithm Idea
Divide the element range into B buckets. Put elements into buckets based on range maps. Sort each bucket independently and gather elements back into the array.
Stable Sorting
Stable (provided the sub-sort algorithm used within buckets is stable)
In-place Memory
Out-of-place (requires separate memory buckets lists)
Source: CP-Algorithms search & sorting reference