by, Subhajit Gorai
16/11/2025

Bucket Sort

in makingin\ making

Time Complexity:

  • Average: O(n+k)O(n + k)
  • Worst: O(n2)O(n^2)
    Space Complexity: O(n+k)O(n + k)
    Stability: Can be stable

When to use:
Input is uniformly distributed over a range.

Algorithm:

  1. Create k empty buckets.
  2. Distribute elements into buckets based on value.
  3. Sort each bucket (e.g., with insertion sort).
  4. Concatenate buckets.
python
def bucket_sort(arr):
  if not arr:
    return arr

  # create buckets
  buckets = [[] for _ in range(len(arr))]

  # put array elements in buckets
  for x in arr:
    index = int(x * len(arr))   # works for 0 <= x < 1
    buckets[index].append(x)

  # sort each bucket and concatenate
  result = []
  for b in buckets:
    result.extend(sorted(b))

  return result

Visualisation, Sorting [7, 3, 5, 2, 9]:

sh
BUCKET SORT VISUALIZATION
==========================

Initial array (using decimals for better demonstration):
+------+------+------+------+------+
| 0.78 | 0.17 | 0.39 | 0.26 | 0.72 |   <-- value
+------+------+------+------+------+
   0      1      2      3      4       <-- index

Note: Using values in range [0, 1) for classic bucket sort
      With 5 buckets, each bucket covers range of 0.2


========================================
STEP 1: CREATE BUCKETS
========================================

Number of buckets = 5 (typically n or √n)
Bucket ranges:
  Bucket 0: [0.0, 0.2)
  Bucket 1: [0.2, 0.4)
  Bucket 2: [0.4, 0.6)
  Bucket 3: [0.6, 0.8)
  Bucket 4: [0.8, 1.0)

Initial buckets (empty):
+---+    +---+    +---+    +---+    +---+
| 0 |    | 1 |    | 2 |    | 3 |    | 4 |
+---+    +---+    +---+    +---+    +---+
 [ ]      [ ]      [ ]      [ ]      [ ]


========================================
STEP 2: DISTRIBUTE ELEMENTS INTO BUCKETS
========================================

Formula: bucket_index = floor(value × num_buckets)

Element 0.78:
  bucket_index = floor(0.78 × 5) = floor(3.9) = 3
  Place in Bucket 3

+---+    +---+    +---+    +------+    +---+
| 0 |    | 1 |    | 2 |    |  3   |    | 4 |
+---+    +---+    +---+    +------+    +---+
 [ ]      [ ]      [ ]     [0.78]      [ ]


Element 0.17:
  bucket_index = floor(0.17 × 5) = floor(0.85) = 0
  Place in Bucket 0

+------+    +---+    +---+    +------+    +---+
|  0   |    | 1 |    | 2 |    |  3   |    | 4 |
+------+    +---+    +---+    +------+    +---+
[0.17]      [ ]      [ ]     [0.78]      [ ]


Element 0.39:
  bucket_index = floor(0.39 × 5) = floor(1.95) = 1
  Place in Bucket 1

+------+    +------+    +---+    +------+    +---+
|  0   |    |  1   |    | 2 |    |  3   |    | 4 |
+------+    +------+    +---+    +------+    +---+
[0.17]     [0.39]       [ ]     [0.78]      [ ]


Element 0.26:
  bucket_index = floor(0.26 × 5) = floor(1.3) = 1
  Place in Bucket 1

+------+    +-----------+    +---+    +------+    +---+
|  0   |    |     1     |    | 2 |    |  3   |    | 4 |
+------+    +-----------+    +---+    +------+    +---+
[0.17]     [0.39, 0.26]      [ ]     [0.78]      [ ]


Element 0.72:
  bucket_index = floor(0.72 × 5) = floor(3.6) = 3
  Place in Bucket 3

+------+    +-----------+    +---+    +-----------+    +---+
|  0   |    |     1     |    | 2 |    |     3     |    | 4 |
+------+    +-----------+    +---+    +-----------+    +---+
[0.17]     [0.39, 0.26]      [ ]     [0.78, 0.72]     [ ]


========================================
STEP 3: SORT EACH BUCKET
========================================
(Using insertion sort for small buckets)

Bucket 0: [0.17]
  Already sorted (single element)
  → [0.17]

Bucket 1: [0.39, 0.26]
  Compare 0.39 and 0.26: 0.26 < 0.39 → swap
  → [0.26, 0.39]

Bucket 2: []
  Empty
  → []

Bucket 3: [0.78, 0.72]
  Compare 0.78 and 0.72: 0.72 < 0.78 → swap
  → [0.72, 0.78]

Bucket 4: []
  Empty
  → []

After sorting each bucket:
+------+    +-----------+    +---+    +-----------+    +---+
|  0   |    |     1     |    | 2 |    |     3     |    | 4 |
+------+    +-----------+    +---+    +-----------+    +---+
[0.17]     [0.26, 0.39]      [ ]     [0.72, 0.78]     [ ]
  ✓            ✓              ✓            ✓           ✓
sorted       sorted        sorted       sorted      sorted


========================================
STEP 4: CONCATENATE ALL BUCKETS
========================================

Concatenate: Bucket 0 + Bucket 1 + Bucket 2 + Bucket 3 + Bucket 4

+------+------+------+------+------+
| 0.17 | 0.26 | 0.39 | 0.72 | 0.78 |
+------+------+------+------+------+
  from    from    from    from    from
  B0      B1      B1      B3      B3


Finally sorted:
-----------------
+------+------+------+------+------+
| 0.17 | 0.26 | 0.39 | 0.72 | 0.78 |
+------+------+------+------+------+


========================================
EXAMPLE WITH INTEGERS
========================================

For integers, we can adapt the algorithm:
Array: [29, 25, 3, 49, 9, 37, 21, 43]
Range: 3 to 49, span = 46
Buckets: 5

Bucket ranges:
  Bucket 0: [3, 12)    → [3, 9]
  Bucket 1: [12, 21)   → [21]
  Bucket 2: [21, 30)   → [21, 25, 29]
  Bucket 3: [30, 39)   → [37]
  Bucket 4: [39, 49]   → [43, 49]

After sorting each bucket:
  Bucket 0: [3, 9]
  Bucket 1: [21]
  Bucket 2: [21, 25, 29]
  Bucket 3: [37]
  Bucket 4: [43, 49]

Result: [3, 9, 21, 21, 25, 29, 37, 43, 49]


Summary:
--------
Time Complexity:
- Average: O(n + k) where k = number of buckets
- Worst: O(n²) if all elements go to one bucket
- Best: O(n) when uniformly distributed

Space Complexity: O(n + k)
I hope these articles helped you even by a little,
Thank you, for continuing till the end!
+
+
+
+