Bucket Sort

Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.

Bucket sort
Class	Sorting algorithm
Data structure	Array
Worst case performance
Average case performance
Worst case space complexity

Example

                              

Elements are distributed among bins

Then, elements are sorted within each bin

Algorithm

BUCKET-SORT(A)

1 n ¬ length[A]

2 for i ¬ 1 to n

3   do insert A[i] into list B[ënA[i]û]

4 for i ¬ 1 to n-1

5   do sort list B[i] with insertion sort

6 concatenate the list B[0],B[1],…,B[n-1] together in order