Counting Sort

Counting sort

General comparison sorting has a lower bound of $\Omega(n\log n)$. Counting sort is not comparison-based: array indices help determine the positions of values.

Visit each integer and increment its corresponding count slot. A slot records how often that integer occurs. Traverse counts in order and output each index value as many times as its count indicates.

This sorts integers but wastes space if the count array starts at zero unnecessarily. For {95,94,91,98,99,90,99,93,91,92}, the maximum is 99 and minimum 90. An array of length 100 would waste slots 0–89.

Use length max−min+1 rather than max+1. The minimum becomes an offset for assigning values to count indices.

Counting sort works well for integers within a modest value range, sometimes outperforming $O(n\log n)$ comparison sorts.

Counting sort

#include <stdio.h>
#include <stdlib.h>

int *counting_sort(int *arr, int n) {
    if (n == 0) {
        return arr;
    }

    int max_val = arr[0];
    int min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }

    int range = max_val - min_val + 1;
    int *counts = (int *)calloc(range, sizeof(int));
    if (counts == NULL) {
        exit(1);
    }

    for (int i = 0; i < n; i++) {
        counts[arr[i] - min_val]++;
    }

    int cnt = 0;
    for (int i = 0; i < range; i++) {
        while (counts[i]--) {
            arr[cnt] = i + min_val;
            cnt++;
        }
    }

    free(counts);
    return arr;
}

int main() {
    int arr[] = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
    int n = sizeof(arr) / sizeof(arr[0]);

    counting_sort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

For $k=max-min+1$, this implementation takes $O(n+k)$ time and $O(k)$ space. It reconstructs integer values alone and cannot directly preserve the stable order of attached records.