Bucket sort is a distribution-based sorting algorithm that works by dividing elements into a fixed number of equally-sized ranges (buckets), sorting each bucket individually, then concatenating the results. It is particularly efficient for uniformly distributed floating-point values in [0, 1) and can approach O(n) average-case time — faster than comparison-based sorts like merge sort or quicksort.
How Bucket Sort Works
- Distribute — Map each element to a bucket based on its value. For a float in [0, 1),
index = (int)(value * n)places it in one of n buckets. - Sort buckets — Apply insertion sort to each bucket. Because the input is roughly uniform, each bucket has ~1 element on average, so insertion sort is O(1) per bucket.
- Gather — Concatenate all buckets left-to-right to form the sorted array.
Trace with 5 elements
Input: 0.72, 0.17, 0.39, 0.26, 0.94 (n=5 buckets) Distribute (index = (int)(val * 5)): Bucket 0 [0.00–0.20): 0.17 Bucket 1 [0.20–0.40): 0.39, 0.26 Bucket 2 [0.40–0.60): empty Bucket 3 [0.60–0.80): 0.72 Bucket 4 [0.80–1.00): 0.94 Sort bucket 1: 0.26, 0.39 Gather: 0.17, 0.26, 0.39, 0.72, 0.94 ✓
C Program for Bucket Sort
#include <stdio.h>
#include <stdlib.h>
void bucket_sort(float arr[], int n)
{
float **buckets;
int *counts;
int i, j, k;
float temp;
buckets = (float **)malloc(n * sizeof(float *));
counts = (int *)malloc(n * sizeof(int));
if (!buckets || !counts) { free(buckets); free(counts); return; }
for (i = 0; i < n; i++) {
buckets[i] = (float *)malloc(n * sizeof(float));
counts[i] = 0;
}
/* Distribute into buckets */
for (i = 0; i < n; i++) {
int idx = (int)(arr[i] * n);
buckets[idx][counts[idx]++] = arr[i];
}
/* Sort each bucket with insertion sort */
for (i = 0; i < n; i++) {
for (j = 1; j < counts[i]; j++) {
temp = buckets[i][j];
k = j - 1;
while (k >= 0 && buckets[i][k] > temp) {
buckets[i][k + 1] = buckets[i][k];
k--;
}
buckets[i][k + 1] = temp;
}
}
/* Gather back into arr */
k = 0;
for (i = 0; i < n; i++) {
int m;
for (m = 0; m < counts[i]; m++)
arr[k++] = buckets[i][m];
free(buckets[i]);
}
free(buckets);
free(counts);
}
int main(void)
{
float arr[] = {0.78f, 0.17f, 0.39f, 0.26f, 0.72f,
0.94f, 0.21f, 0.12f, 0.23f, 0.68f};
int n = 10;
int i;
printf("Before: ");
for (i = 0; i < n; i++) printf("%.2f ", arr[i]);
printf("\n");
bucket_sort(arr, n);
printf("After: ");
for (i = 0; i < n; i++) printf("%.2f ", arr[i]);
printf("\n");
return 0;
}
Output
Before: 0.78 0.17 0.39 0.26 0.72 0.94 0.21 0.12 0.23 0.68 After: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94
How to Compile and Run
gcc -ansi -Wall -Wextra bucket.c -o bucket
./bucket
Code Walkthrough
- Dynamic allocation —
mallocis used throughout so the code works under strict ANSI C without variable-length arrays (VLAs). Each bucket is allocated to hold up to n elements (worst-case: all fall in one bucket). - Distribution —
(int)(arr[i] * n)maps a float in [0, 1) to an integer index in [0, n-1]. Values of exactly 1.0 would overflow to index n — guard against this if your data may include 1.0. - Insertion sort per bucket — O(k²) per bucket where k is the bucket size. For uniform data k ≈ 1, making each sort O(1).
- Gather and free — Buckets are freed inside the gather loop to avoid a separate cleanup pass.
Time and Space Complexity
| Case | Time | Space | When it occurs |
|---|---|---|---|
| Best / Average | O(n + k) | O(n + k) | Uniform distribution, k = n buckets |
| Worst | O(n²) | O(n) | All elements fall in one bucket |
k = number of buckets (usually set to n). For uniform input the average case is O(n), beating all comparison-based sorts. For skewed input (all elements near the same value), performance degrades to O(n²) due to insertion sort on a single large bucket.
When to Use Bucket Sort
| Use bucket sort when… | Prefer another sort when… |
|---|---|
| Input is floating-point in a known range | Input range is unknown or unbounded |
| Distribution is roughly uniform | Distribution is highly skewed |
| Average-case O(n) performance matters | Worst-case guarantees are required (use merge sort) |
Related Programs
- Merge Sort in C — O(n log n) worst case, stable sort
- Insertion Sort in C — used inside each bucket
- Bubble Sort in C
- Radix Sort in C
- Pointers in C – Complete Guide — malloc and pointer-to-pointer
Recommended Books
- The C Programming Language – Kernighan & Ritchie (India) | Amazon.com
- C Programming: A Modern Approach – K.N. King (India) | Amazon.com
Practice sorting algorithms with the C Programming Quiz App — 500+ MCQs covering arrays, sorting, and more.
Download on Google Play →