AlgoScope

Bucket Sort

Scatter values into equal value ranges, sort each small bucket, gather in order: linear on even data.

Sorting, algorithm, intermediate
42 into bucket 25-49.012345678in0-2425-4950-7475-99out427882361975305542

More Sorts: Bucket sort into four ranges

Decision, step 2 of 19

42 x 4 / 100 = 1, so 42 goes into bucket 25-49 as its first value.

How more sorts works

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

  • No: Comparison based
  • Yes: Stable
  • No: In place
  • No: Adaptive
  • No: Online

Taught by the same lesson

More Sorts covers these too, in the same run.