A Generic Implementation of Counting Sort

Posted on August 17, 2017 Updated on August 17, 2017

What is “Counting Sort”?

Counting Sort is a super fast sort algorithm that only works for certain types of data.

• It is only useful if you have a relatively small range of values to sort
• Even if there you have a large number of items to sort

For example, if you have a large list of “Person” objects, and each Person has an age between 1 and 100, then counting sort would be useful. Because what you are sorting on, age, has a relatively small range. The ages are repeated a lot, i.e. you will probably have a lot of Persons with age=18, a lot with age=65, etc.

For a counter example, assume each Person has a social security number; this would not be good use for Counting Sort, because there shouldn’t be any repeated SSNs.

Algorithm Speed

• Counting Sort runs in O(n) (refer to Big O Notation for an explanation)
• Which is superior to most other sorts, which run in O(n ∙ ln(n)) time

Counting Sort is only necessary in a special situations where you have need  maximum efficiency, typically big data sets or other situations where you sort a lot.

Concepts Covered in this Post

• Counting Sort
• Generic Methods
• Extension Methods
• C# delegates using ‘Func’ declaration

First, The Code, Then The Explanation

using System;
using System.Collections.Generic;

namespace CountingSortExample {
  public static class CountingSortExt {
    public static IList<T> CountingSort<T>(this IList<T> sortMe,
                                           Func<T, int> sortProp) {
      List<int> buckets = new List<int>();
      for (int i = 0; i < sortMe.Count; i++) {
        int theVal = sortProp(sortMe[i]);

        //Increase the bucket size, if necessary
        for (int j = buckets.Count; j <= theVal; j++)
          buckets.Add(0);

        buckets[theVal]++;
      }

      int[] startIndex = new int[buckets.Count];
      for (int j = 1; j < startIndex.Length; j++) {
        startIndex[j] = buckets[j-1] + startIndex[j-1];
      }

      T[] result = new T[sortMe.Count];
      for (int i = 0; i < sortMe.Count; i++) {
        int theVal = sortProp(sortMe[i]);
        int destIndex = startIndex[theVal]++;
        result[destIndex] = sortMe[i];
      }

      return result;
    }
  }
}

Usage

List<Person> _PersonList;      //List populated elsewhere
//Now do the work:
IList<Person> sorted = _PersonList.CountingSort(p => p.Age);

Notes on Generic Aspects of My Implementation

• public static class CountingSortExt  – This is an extension method, so it must be a static class
  • Using an extension method allows the syntax immediately above, i.e. _Personlist.CountingSort…
• public static IList<T> CountingSort – Static again because it is an extension method
  • T is a placeholder for the class type being sorted
• Func<T, int> sortProp – an anonymous function that allows the caller to specify the field used to perform the sort with
  • When you invoke it, it will look like this: p => p.Age
  • Which means “Use the age field for sorting”

Brief Discussion of the Algorithm

Counting sort works by:

1. Counting how many there are of each age. There is one person with age 7, seven persons with age 18, two persons with age 21 and five persons with age 65.
2. We can use the counts to compute the destination index to move each person to
3. For example, since there is only one seven-year-old, we know to move the first eighteen-year-old into slot 2.

Another Example

Because I implemented my method as a generic method, you can sort anything that has an int property, such as sorting a list of strings by length. You simply need to pass a lambda expression indicating the field/property to sort on, such as a string length property, as shown in the sample below:

List<string> stringList = new List { 
	"adsf",
	"adsfl;jkadsf",
	"qwerp9oui",
	"a",
	";ljsdfqweroiusd",
	"zcxv,mnzxcvnm,k"
};
IList<string> sortedString = stringList.CountingSort(w => w.Length);
foreach(string s in sortedString)
	Console.WriteLine(s);

Potential Modification

Note that my code works well when the field/property being sorted is close to 0. If that is not the case for you, you could replace my list ‘Buckets’ with a dictionary, or other type of hash list. Otherwise, if you have high values for the sorting field/property, you will allocate a large amount of memory for Buckets.

Download the Code

You can download my code from my DropBox account; they will ask you to set-up a free account for the privilege of downloading it.