Bucket Sort Algorithm

3 min readSep 23, 2022

A non in-place sorting algorithm that separates elements into multiple buckets. Each bucket is sorted individually by any sorting algorithm. Finally, combine sorted buckets to yield a sorted array. On average, bucket sort runs in O(n+k) time. In the worst case, it is O(n²) time if elements are allocated at the same bucket.

Table of Contents· How Does Bucket Sort Algorithm Work?
· Graphical Explanation
  ∘ positive array
  ∘ array with negative values
· Code Implementation
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How Does Bucket Sort Algorithm Work?

Bucket sort algorithm assigns elements to several buckets(or called bins) firstly. The elements are grouped in different buckets and not sorted yet. Then those buckets are sorted individually using any sorting algorithm. Finally, gather sorted buckets to form a sorted output.

Graphical Explanation

step1:
a. get the maximum and minimum values in the unsorted array
b. calculate required bucket size

bucket size = floor((maxValue - minValue) / len(array)) + 1

You can use different formula to determine bucket size based on your application.

step2: allocate elements into their corresponding buckets

bucketIdx = floor((element - minValue) / len(array))

You can use different formula to assign elements into buckets based on your application.

step3: sort individual buckets (using insertion sort)

You can use any sorting algorithm to sort buckets.

step4: combine sorted buckets to form a sorted array

positive array

array with negative values

Code Implementation

Complexity

Time: Best O(n+k), Average O(n+k), worst O(n²)

Best case: elements are uniformly distributed in the bucket
Worst case: elements are allocated at the same bucket

Space: O(n+k)
n: the total number of elements in the input array
k: the total number of buckets

Pseudocode

# find the maximum and minimum value
maxValue, minValue = max(array), min(array)# calculate number of buckets(bucket size)
numberOfBuckets = floor((maxValue - minValue)/n) + 1# create empty buckets
buckets# allocate elements to their corresponding bucket
for element in array:
    bucketIdx = (element - minValue)/len(array)
    append element to buckets[bucketIdx]# sort individual buckets using insertion sort
for bucket in buckets:
    insertionSort(bucket)# combine sorted bucket to generate a sorted output
sortedIdx = 0
for bucket in buckets:
   for element in bucket:
      array[sortedIdx] = element
      sortedIdx += 1

Golang

Python

You can access the source code here.

Insertion Sort Algorithm

Other sorting algorithms: