Counting sort is likely one of the simplest sorting algorithms that can be used to sort a list of integers and is also used as a key component of Radix Sort. Both were invented/discovered by Harold Seward. In this article I will both explain and code, Counting Sort in C.
Counting Sort
Counting Sort is very basic to implment, the sole purpose of the algorithm is to sort integers of a given list and will outperform general purpose sorting algorithms. For example, given the array {1, 3, 5, 2, 4, 1}, applying the Counting Sort algorithm to the array should give you: {1, 1, 2, 3, 4, 5}. The algorithm works by using the following steps:
- Initializing a counting array to all zeros, the size of the array being equal to the maximum integer in the list.
- Iterate through the input array (the array you wish to sort) adding to the count of the corresponding counting array index. That is to say, if you were iterating over the integer 5 in the input array, you would add to the count of index 5 in the counting array.
- Transfer the count of each index in the counting array back to the input array (overriding previous values), there by making the input array the output array (and saving space).
Example
Input array {3, 4, 3, 2, 1}, the maximum entry is 4 and size is 5
Create a counting array {0, 0, 0, 0}, size is 4
Iterate over the input array, and add count to the appropriate index:
{3, 4, 3, 2, 1} -> {0, 0, 1, 0}
{3, 4, 3, 2, 1} -> {0, 0, 1, 1}
{3, 4, 3, 2, 1} -> {0, 0, 2, 1}
{3, 4, 3, 2, 1} -> {0, 1, 2, 1}
{3, 4, 3, 2, 1} -> {1, 1, 2, 1}
The counting array is currently {1, 1, 2, 1}, we now can override the input array to create our sorted list.
{0, 1, 2, 1} -> {1, 4, 3, 2, 1}
{o, o, 2, 1} -> {1, 2, 3, 2, 1}
{o, o, 1, 1} -> {1, 2, 3, 2, 1}
{o, o, o, 1} -> {1, 2, 3, 3, 1}
{o, o, o, o} -> {1, 2, 3, 3, 4}
We are now done, the input (now output) array consists of {1, 2, 3, 3, 4} in the proper order.
- Time: O(n + k), where n is the number of entries and k is the maximum number
- Space: O(n + k), where n is the number of entries and k is the maximum number
Code
Summary
Unfortunately, the simplicity of this algorithm is also its downfall and many programmers do not need to sort integers.. Or at least that is what they believe. Often it is possible to reduce a problem to an integer problem and from there use counting sort or radix sort (sometimes it is practical to add a layer of abstraction if you can sort something much faster). A quick Google search can find many results, one interesting example related to a Particles-in-Cell simulation.
You might want to add that the whole reason to have a special sort for integers is because non-comparison based sorts can beat the lower bound on general sorting algorithms, O(n lg n).
Good idea I’ll add that now.
hi! I’ve been going through your articles as I try to develop my C skills. I was just wondering whether the counting sort algorithm will have any downside as to performance when dealing with large integers, as it would have to allocate an array with the maximum number, e.g. sorting [4, 8, 20181] will create an array of int counting_array[20181]. i did try this, but did not notice any lag. any thoughts?
To be honest I don’t know if there should (or should not) be lag. The internals of each operating system, compiler and hardware will effect how the algorithm is handled. That being said, I would expect there to be some lag as the integer values become larger, how much, I couldn’t say.
thanks!