Counting sort in C#

Counting sort - overview

Counting sort (or histogram sort) is a linear integer sorting algorithm. It counts the number of elements that have the same value in the input array, puts the number of items in a a auxilliary counting array and then uses arithmetic to get the position of each value in the output array. The algorithm was invented by Harold H. Seward in 1954.

Counting sort does not use any comparisons, so it is not a comparison sort. Instead, it uses the values of the elements in the input array as indexes in an array used for counting.

A useful property of counting sort is that it is stable. This property is important when there is satellite data belonging to the elements being sorted.

The stability property is useful for another reason. In radix sort the counting sort algorithm is often used as a subroutine. In order to get Radix sort to work it is required that counting sort is stable. 

Description of the counting sort algorithm

Lets assume that we have an input array containing n values in the range [0..k]. Counting sort first creates an auxilliary counting array (with  k+1 elements) to hold frequencies of the elements in the input array. It then loops through all values in the input array and for each value, it uses that value as index in the counting array and increments that value by 1. For example if the value in the input array is 17, then it would execute countingArray[17]++ for each value.

After this first loop the counting array now holds the frequencies for all values in the input array.

In the next step the counting array is recalculated so that at position i, the value holds information about how many input elements that are less than or equal to the element i. In other words, the element at index=i holds the index position j of where the value i should be put in the output array. If using a zero indexed array we take the number j and decrease by 1, and then we get the final position.

Next an array for the output is created. The input array is then looped through, and for each value v it retrieves the position of where v should be placed in the output array. The value is retrieved from the recalculated counting array. Then it decreases the value in the counting array by 1.

Computational complexity

Counting sort has has a complexity of  O(n + k), where n is the size of the sorted array and k is the size of the helper array.

Example of an implementation of counting sort in C#

    private void SortArrayWithCountingSort()
    {
        int[] arrayToSort = { 2, 6, 6, 10, 10, 3 };
        int[] sorted = CountingSort(arrayToSort);

        // PrintResult(sorted);
    }

    private int[] CountingSort(int[] array)
    {
        int[] count = new int[11];

        for (int i = 0; i < array.Length; i++)
        {
            int value = array[i];
            count[value]++;
        }

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

        int[] sorted = new int[array.Length];

        for (int i = array.Length - 1; i >= 0; i--)
        {
            int value = array[i];
            int position = count[value] - 1;
            sorted[position] = value;

            count[value]--;
        }

        return sorted;
    }