Bucket Sort

by codecrucks · Published 12/09/2021 · Updated 08/06/2022

Bucket sort is also known as bin sort. It is a sorting algorithm that divides an array’s items into a number of buckets. The buckets are then sorted one at a time, either using a separate sorting method or by recursively applying the bucket sorting algorithm.

Assumption : Input data is generated by some random process and uniformly distributed in the range of [0, 1).

Bucket sort sorts the data by partitioning them into n buckets. Each number is stored in an appropriate bucket. Numbers in a bucket are sorted using some linear time algorithm. Inputs are uniformly distributed so it is less likely to fall many numbers in a single bucket.

Bucket sort operates in two stages:

Scatter: Distribute all the elements in their respective buckets. Sort all the buckets
Gather: Visit all buckets in order and put all the data in original array

Example of Bucket Sort

Example: Trace bucket sort with following data {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68}.

Solution:

Ten bins/buckets are created and elements of array A is inserted in the appropriate bin number integer of [n*A[i]]. Following diagram shows the Input data pattern and sorted bins. Insert element in a linked list using insertion sort.

Read values from each bucket in same order, so sorted data would be B {0.12, 0.17, 0.21, 0.23, 0.28, 0.39, 0.68, 0.72, 0.78, 0.94}.

Example: Sort the array A {0.23, 0.65, 0.11, 0.37, 0.45, 0.63, 0.18, 0.87, 0.92, 0.25} using bucket sort.

Solution:

Ten buckets are created and elements of array A is inserted in the appropriate bucket number integer of [n*A[i]]. Following diagram shows the Input data pattern and sorted buckets. Insert element in a linked list using insertion sort.

Read values from each bucket in the same order, so sorted data would be B{0.11, 0.18, 0.23, 0.25, 0.37, 0.45, 0.63, 0.65, 0.87, 0.92}

Algorithm of Bucket Sort

Algorithm BUCKET_SORT(A) 
// A is an array of size n

Create n buckets represented by B
for i ← 1 to n do
  Insert A[i] into bucket B[n*A[i]]
end

for i ← 1 to n do
  sort each bucket i using insertion sort
end
Concate all buckets into sorted order

Complexity Analysis

This technique is most useful when the input is evenly spread throughout a range.
Adjacent keys (elements with almost similar values) are placed in one bucket, which makes distribution uneven. Some buckets will contain more elements, while others will have fewer elements.
The worst case occurs when all elements create a tight cluster and fall into the same bucket. In this case, the running time of the algorithm would be O(n²)
If the size of each bucket is one, the performance of bucket sort reduces to counting sort.
In general, the time complexity of bucket sort is O(n + m), where n is the number of elements in the array and m is the range of input values.

Advantages of Bucket Sort

Because of the uniform distribution, it is asymptotically fast.
It reduces the number of comparisons.
When compared to bubble sort, it is faster.

Limitations of Bucket Sort

It is not suitable for sorting arbitrary strings.
It is only good for sorting data uniformly distributed over the range [0, 1].
It is not an in-place sorting because the buckets require additional space to be sorted.
It is ineffective if we have a huge array since it increases the cost.
Prior knowledge of the greatest element is required.

Some Popular Sorting Algorithms

Following are the few popular sorting algorithms used in computer science:

Additional Reading: Visualization