基数ソートは、配列の要素を、その桁数に応じてグループ分けした後に、整列を行うアルゴリズムである。グループ分け後のソートアルゴリズムは、クイックソート、バケットソート、計数ソートなどのアルゴリズムを利用する。次の例では、要素の値の桁数に応じてグループ分けを行い、各グループに対して計数ソートを行うサンプルコードである。

#include <stdio.h>

void countSort(int array[], int array_size, int exp) {

    int sorted_array[array_size];
    int count[10] = {0};

    for (int i = 0; i < array_size; i++) {
        count[(array[i] / exp) % 10]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = array_size - 1; i >= 0; i--) {
        sorted_array[count[(array[i] / exp) % 10 ] - 1] = array[i];
        count[(array[i] / exp) % 10]--;
    }

    for (int i = 0; i < array_size; i++) {
        array[i] = sorted_array[i];
    }
}

void radixSort(int array[], int array_size) {

    // find the maximum value in the array
    int max = array[0];
    for(int i = 1; i < array_size; i++) {
        if(array[i] > max) {
            max = array[i];
        }
    }

    // sorting based on 10^i, where i = 1, 2, ...
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(array, array_size, exp);
    }
}

int main (void) {

    int i;
    int array[] = {3, 0, 11, 16, 11, 28, 132, 135, 339, 8000, 1203, 2040};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    radixSort(array, sizeof(array) / sizeof(array[0]));

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}