Hi, I took the liberty of looking around to see what other interesting sorting methods are out there. One in particular caught my eye. The sorting algorithm CountingSort. This method sorts with an effort $O(n)$. That's also the reason why I'm going to talk about this method.

What is Counting-Sort

CountingSort is small in-place method, because it needs for the sorting minimum as much memory as the input list is large. This method works with indices, so it works with array index.

Prerequisites

For CountingSort to work at all, and to work with an effort $O(n)$, the following must be given:

• All numbers must be greater than or equal to $0$.
• The largest number in the list must be known.

CountingSort works in such a way that the maximum value is determined from the input array. This is incremented by 1 to create the counting array. This array is used to determine the frequencies of the individual numbers in the input list. That is also already the magic behind it.

Each number from the list represents the index in the counting list. At the end, the respective index, which is greater than 0, is written into the input list. Here, the position is combined with the frequency.

We can see how this works here in this animation.

Implementing Counting Sort

Now let's implement the whole thing. The implementation is done in C++, and is very simple. First of all we need a method, which outputs the arrays.

void show(std::vector<int> v)
{
    std::cout << "[";
    for(int i = 0; i < v.size(); i++)
    {
        std::cout << v[i] << ", ";
    }
    std::cout << "]" << std::endl;
}

Now we need a function that will return the maximum from the array. The getMax function simply goes through all the elements and finds the largest value in the array.

int getMax(std::vector<int> v)
{
    int max = 0;
    for(int i = 0; i < v.size(); i++)
    {
        if(v[i] > max)
            max = v[i];
    }

    return max;
}

Here, a variable max is created, which is first set to 0. Each value from the array is compared with the variable, obs is larger. If it is, max is set to the larger value. At the end, the value max is returned.

That's all that is needed, now we come to the procedure itself.

void sort(std::vector<int> &v)
{
    int max = getMax(v);
    std::vector<int> count;
    count.resize(max+1, 0);
    for(int i = 0; i < v.size(); i++)
    {
        count[v[i]]++;
    }

    int v_pos = 0;
    for(int i = 0; i < count.size(); i++)
    {
        if(count[i] > 0)
        {
            for(int j = 0; j < count[i]; j++)
            {
                v[v_pos] = i;
                v_pos++;
            }
        }
    }
}

If we look at the code, we see that the maximum is determined here first. For this, the counting array is created, which has $maximum + 1$ entries. With this we can now count the numbers from $0 - n$. If we would not increase the maximum by 1, we could only count up to $n-1$.

In the first For loop, the frequency of each number is determined and stored at the respective index in the counting array.

In the 2nd loop, we go through the counting array, and write each index, whose value is greater than 0, into the input list. If the value is greater than 0, the index is written to the input list as many times as the number of times. After each entry, it goes 1 to the right.

The Main for testing the procedure looks like this.

int main()
{
    std::vector<int> v;
    for(int i = 0; i < 10; i++)
    {
        v.push_back(rand() % 10);
    }
    show(v);
    sort(v);
    show(v);
    return 0;
}

If we run the whole thing, the output looks something like this.

~$ g++ -o sort *.cpp && ./sort
[3, 6, 7, 5, 3, 5, 6, 2, 9, 1, ]
[1, 2, 3, 3, 5, 5, 6, 6, 7, 9, ]

I hope I could give a little insight, to CountingSort 😄