Bucket sort in C: solved exercise

If you searched for a solved bucket sort exercise in C, here is the full implementation: it distributes elements into buckets, sorts each bucket with insertion sort, and concatenates them, achieving expected O(n) when data is uniformly distributed in [0, 1).

Bucket sort is one of the few sorting algorithms that breaks the Ω(n log n) comparison-sort barrier, but only under the assumption of uniform distribution.

Problem statement

Sort the array {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68} using bucket sort with 10 buckets. Show the bucket contents before sorting them and the final array.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdlib.h>

#define N  10
#define NB 10 /* number of buckets */

typedef struct Node {
    double val;
    struct Node *next;
} Node;

/* Sorted insertion into the bucket's linked list */
void insert_sorted(Node **bucket, double val) {
    Node *node = malloc(sizeof(Node));
    node->val  = val;
    node->next = NULL;

    if (!*bucket || val < (*bucket)->val) {
        node->next = *bucket;
        *bucket    = node;
        return;
    }
    Node *cur = *bucket;
    while (cur->next && cur->next->val <= val) cur = cur->next;
    node->next = cur->next;
    cur->next  = node;
}

void free_bucket(Node *bucket) {
    while (bucket) { Node *t = bucket; bucket = bucket->next; free(t); }
}

void bucket_sort(double arr[], int n) {
    Node *buckets[NB] = {NULL};

    /* Distribute */
    for (int i = 0; i < n; i++) {
        int idx = (int)(arr[i] * NB);
        if (idx >= NB) idx = NB - 1;
        insert_sorted(&buckets[idx], arr[i]);
    }

    /* Show buckets */
    for (int i = 0; i < NB; i++) {
        printf("bucket[%d]: ", i);
        for (Node *p = buckets[i]; p; p = p->next) printf("%.2f ", p->val);
        printf("\n");
    }

    /* Concatenate */
    int pos = 0;
    for (int i = 0; i < NB; i++) {
        for (Node *p = buckets[i]; p; p = p->next) arr[pos++] = p->val;
        free_bucket(buckets[i]);
    }
}

int main(void) {
    double a[N] = {0.78, 0.17, 0.39, 0.26, 0.72,
                   0.94, 0.21, 0.12, 0.23, 0.68};
    bucket_sort(a, N);
    printf("\nSorted: ");
    for (int i = 0; i < N; i++) printf("%.2f ", a[i]);
    printf("\n");
    return 0;
}

Expected output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
bucket[0]: 
bucket[1]: 0.12 0.17 
bucket[2]: 0.21 0.23 0.26 
bucket[3]: 0.39 
bucket[4]: 
bucket[5]: 
bucket[6]: 0.68 
bucket[7]: 0.72 0.78 
bucket[8]: 
bucket[9]: 0.94 

Sorted: 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94 

Common mistakes

Not freeing bucket memory: each bucket is a linked list that must be freed with free to avoid memory leaks.
Not checking that malloc returns NULL: allocation can fail on low-memory systems.
Computing the bucket index with (int)(val * NB) without clamping: if val == 1.0, the index would be NB, out of bounds.
Assuming bucket sort is always O(n): in the worst case (all elements in the same bucket) it degenerates to O(n²) with insertion sort as the inner algorithm.

Practical use

Bucket sort is used in rendering systems (distributing particles by depth), in histogram computation, and in the distribution phase of radix sort. It is especially efficient when data comes from a uniform distribution, such as randomly generated floating-point numbers in [0, 1).

Recommended next exercise

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

Why can bucket sort be O(n) if it uses an inner insertion loop?

Because when data is uniformly distributed, the expected number of elements per bucket is n/k (where k is the number of buckets). With k ≈ n, each bucket has on average 1 element, and insertion sort on each bucket is O(1). The total across all buckets is O(n) in the average case.

How many buckets should I use?

The general rule is to use as many buckets as elements (k = n), giving expected O(n). Fewer buckets increase the insertion time per bucket; too many buckets increase the overhead of managing empty buckets.

Can I use bucket sort with integers?

Yes, either by normalizing values to [0, 1) or by using the value directly as a bucket index (equivalent to counting sort for small ranges). For integers in [min, max], the bucket index is (val - min) * NB / (max - min + 1).