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

Counting Sort is an efficient sorting algorithm particularly suitable for sorting large sets of small integers. Unlike comparison-based algorithms, Counting Sort operates in linear time, making it ideal for scenarios where the range of input data is limited.

Overview of Counting Sort

Counting Sort works by counting the number of occurrences of each unique element in the input array. It then uses these counts to determine the correct position of each element in the sorted output. This approach ensures that the sorting process is both fast and stable, preserving the original order of equal elements.

Implementing Counting Sort in C#

Below is a step-by-step implementation of Counting Sort in C# for sorting large arrays of small integers.

Step 1: Initialize the Counting Array

Create an array to hold counts of each integer within the range. For small integers, this array will be relatively small.

Step 2: Count the Occurrences

Iterate through the input array, incrementing the count for each element in the counting array.

Step 3: Generate the Sorted Array

Use the counts to reconstruct the sorted array by placing each element the number of times it appears.

Sample C# Implementation

Here is a complete example of Counting Sort in C#:

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

    // Count occurrences
    for (int i = 0; i < array.Length; i++)
    {
        counts[array[i]]++;
    }

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

In this implementation, maxValue should be the maximum value present in the input array. This ensures the counting array is appropriately sized.

Advantages of Counting Sort

Linear time complexity for small ranges
Stable sorting algorithm
Efficient for large datasets with limited value ranges

Limitations

Not suitable for large ranges of data
Requires additional memory proportional to the range of input
Only works with non-negative integers

Counting Sort is a powerful tool when used appropriately. Its simplicity and speed make it a valuable algorithm in the toolbox of any programmer dealing with large sets of small integers.

Table of Contents