Bucket Sort

Distributes elements into buckets, sorts each bucket, then concatenates the results.

Step 1 of 36

Starting Bucket Sort with 3 buckets. Distribute elements, sort each bucket with insertion sort, then concatenate.

Comparisons

Moves

▶Algorithm

BucketSort(arr, k):
create k empty buckets
for each element x in arr:
place x in bucket[floor(k*(x-min)/range)]
for each bucket b:
insertion sort bucket b
concatenate all buckets into arr
// sorted

Legend

Being placed

Written back

Sorted

Unsorted

The auxiliary section shows 3 buckets side-by-side. Elements are distributed by value range, sorted within each bucket using insertion sort, then concatenated.

1 / 36Speed