Implementing Counting Sort for Sorting Large Sets of Small Integers in C#

When your sorting task involves large arrays of small integers—such as grades, ages, or categorical codes—the classic comparison-based algorithms like QuickSort or MergeSort can feel like overkill. These algorithms run in O(n log n) time, but if the range of possible values is limited, you can sort in linear O(n + k) time with Counting Sort. This non-comparison sorting algorithm leverages the fact that you can count occurrences rather than compare elements, delivering a stable sort that is both simple and blazingly fast for the right inputs.

How Counting Sort Works

Counting Sort exploits the knowledge that the input values are integers drawn from a small range [0, k]. Instead of pairwise comparisons, it builds a frequency histogram of the values and then uses that histogram to place each element in its correct sorted position.

The Basic Approach: Direct Reconstruction

The simplest version of Counting Sort works in two passes:

1. Count frequencies – Iterate through the input array and increment a counter for each value you see.
2. Overwrite the input – Walk through the counter array from smallest to largest and, for each value, write it back into the input array as many times as its count.

This yields a sorted output but does not preserve the relative order of duplicates (it is not stable). Stability matters when you sort on a key while keeping the original order of records with equal keys. The stable variant, described next, is the one most commonly used in practice.

The Stable Variant: Cumulative Counts

To make Counting Sort stable, we add a third pass:

1. Count frequencies as before.
2. Transform the frequency array into a cumulative count array. After this step, counts[i] holds the number of elements ≤ i.
3. Iterate the input array in reverse (from last element to first). For each element, use its cumulative count to find its position in the output array, place it, and decrement the count.

Because we traverse in reverse, the relative order of equal elements is preserved. The output array is separate from the input, so this version uses O(n) additional space for the output, whereas the basic version can sort in-place by overwriting the input.

Implementing Counting Sort in C#

Below are two C# implementations: the basic in-place version (for scenarios where stability is unnecessary) and the stable version that uses an auxiliary array. Both require knowing the maximum value in advance.

Basic (Non‑Stable) Counting Sort

This variant sorts the input array directly without an extra output buffer. It is memory‑efficient but not stable.

public static void CountingSortBasic(int[] array, int maxValue)
{
    int[] counts = new int[maxValue + 1];

    // Count each element's frequency
    for (int i = 0; i < array.Length; i++)
    {
        counts[array[i]]++;
    }

    // Overwrite the original array in sorted order
    int index = 0;
    for (int value = 0; value <= maxValue; value++)
    {
        while (counts[value]-- > 0)
        {
            array[index++] = value;
        }
    }
}

Stable Counting Sort

The stable version requires an output array of the same size as the input. It also uses cumulative counts to position elements correctly.

public static int[] CountingSortStable(int[] array, int maxValue)
{
    int[] counts = new int[maxValue + 1];
    int[] output = new int[array.Length];

    // Step 1: Count occurrences
    foreach (int num in array)
    {
        counts[num]++;
    }

    // Step 2: Transform counts to cumulative counts
    for (int i = 1; i <= maxValue; i++)
    {
        counts[i] += counts[i - 1];
    }

    // Step 3: Build the output array (iterate input in reverse for stability)
    for (int i = array.Length - 1; i >= 0; i--)
    {
        int value = array[i];
        output[counts[value] - 1] = value;
        counts[value]--;
    }

    return output;
}

In both implementations, maxValue is the largest integer that appears in the array. If the true maximum is unknown, you can compute it with a preparatory scan (O(n)). The stable version returns a new sorted array, leaving the original unchanged.

Complexity Analysis

Let n be the number of elements and k = max – min + 1 (the range of possible values).

• Time: Counting Sort runs in O(n + k) time. The Counting phase is O(n), the cumulative prefix is O(k), and the reconstruction is O(n). When k is O(n), the algorithm is linear.
• Space: The basic version uses O(k) extra space for the count array. The stable version uses O(n + k) because it also allocates the output array. This makes Counting Sort unsuitable when the range is large relative to the number of items.
• Comparison with other sorts: Comparison‑based sorts like QuickSort and MergeSort require at least O(n log n) comparisons. For small k (e.g., k < 10,000 and n > 100,000), Counting Sort can be orders of magnitude faster.

Variations and Extensions

Handling Negative Integers

Counting Sort natively works with non‑negative integers. To handle negative values, shift the entire range so the minimum becomes zero. For instance, if numbers range from -1000 to 1000, offset every element by +1000. The count array then has size max - min + 1.

public static int[] CountingSortWithNegative(int[] array)
{
    if (array.Length == 0) return array;

    int min = array.Min();
    int max = array.Max();
    int range = max - min + 1;

    int[] counts = new int[range];
    int[] output = new int[array.Length];

    foreach (int num in array)
        counts[num - min]++;

    for (int i = 1; i < range; i++)
        counts[i] += counts[i - 1];

    for (int i = array.Length - 1; i >= 0; i--)
    {
        int value = array[i];
        output[counts[value - min] - 1] = value;
        counts[value - min]--;
    }

    return output;
}

Mapping Non‑Integer Keys

Counting Sort requires integer keys. If your data consists of characters (bytes), or enumerations that can be cast to integers, you can still apply it. For larger objects, you can extract an integer key and sort the objects accordingly—this is exactly how Radix Sort often uses Counting Sort as its inner subroutine.

Radix Sort Combo

Radix Sort processes digits (or bits) individually, and Counting Sort is the natural choice for each pass when the base (e.g., 10 or 256) is small. This allows linear‑time sorting of arbitrary integers, not just small ones.

Practical Considerations in C#

Memory Footprint and Large k

The biggest pitfall is allocating a count array larger than the available memory. For example, sorting 1,000 elements with a range of 1,000,000 wastes space. Always verify that k is not orders of magnitude bigger than n—otherwise use a comparison sort or a hybrid approach.

Parallelism and Span<T>

For extremely large arrays, you can parallelize the counting phase by partitioning the input across threads. Each thread counts its segment into a private array, and then the partial results are aggregated. Using Span<int> and stackalloc for the count array can reduce heap allocations when the range is small.

Edge Cases

• Empty array – return immediately.
• Single element – sorting is trivial.
• All identical values – the count array has one non‑zero entry; reconstruction runs in O(n).
• Large range but sparse data – Counting Sort becomes inefficient because most count entries are zero. Consider a hash‑based counting approach or Bucket Sort.

Performance Recommendations

Use Counting Sort when you know the input integers fall into a small range (e.g., grades 0–100, ages 0–120, or error codes 0–255). For larger ranges, consider Radix Sort or a hybrid that falls back to QuickSort for high‑range partitions.

When to Use Counting Sort (and When Not To)

Situation	Recommendation
Small integer range (k ~ n)	Excellent choice – linear time, simple code.
Large integer range (k >> n)	Avoid – memory waste and O(k) overhead.
Need stability	Use the stable variant (cumulative counts).
Strings or objects	Consider Radix Sort or a comparison sort.
Extremely large datasets	Counting Sort can be parallelized; but watch memory.

Benchmarking and Performance

In a typical benchmark with n = 1,000,000 and k = 1,000, Counting Sort completes in about 20–30% of the time taken by Array.Sort (which uses introsort). The gap widens as k decreases. Below is an approximate comparison (execution times on a modern CPU with .NET 8):

n = 1,000,000  |  k = 1,000
Array.Sort (QuickSort variant) : 68 ms
CountingSortBasic              : 12 ms
CountingSortStable             : 18 ms

When the range grows to 10,000, Counting Sort still wins, but the margin narrows. For k = 100,000, the memory overhead (≈ 400 KB for the count array) begins to hurt CPU cache, and performance can degrade.

Conclusion

Counting Sort is a deceptively simple algorithm that delivers linear performance when data fits its constraints. For C# developers dealing with large arrays of small integers, it is a valuable tool that can dramatically reduce sorting time. Keep an eye on the range of your data: if it is small and known, Counting Sort will outpace any comparison‑based alternative. For more general‑purpose sorting, use the built‑in Array.Sort, but always be ready to drop in Counting Sort when the numbers line up—literally and figuratively.

For further reading, consult the Wikipedia article on Counting Sort, the Microsoft docs on Array.Sort, and a practical guide from GeeksforGeeks.