Radix sort in C#

Radix sort - overview

Radix sort is a non-comparative technique for ordering a list of positive integers. It dates back to 1887 when Herman Hollerith invented a machine that could sort punchcards using the very same algorithm. That makes it one of the oldest sorting algorithms.

Radix sort works in a pretty straight-forward way and is quite efficient compared to for example the comparison based algorithms.

Radix sort is actually a category of sorting algorithms, not just a single algorithm. There are two types of radix sorts: LSD (least significant digit) and MSD (most significant digit). Here we will mostly consider the LSD variant of the algorithm.

Radix sort is a stable sorting algorithm

Radix sort is an example a a stable sorting algorithm. A sorting algorithm is said to be stable if two objects with the same keys appear in the exact same order in the sorted output array as they appear in the input array.

Computational complexity

The algorithms efficiency is O(kn) for n keys which consists of k number of digits or less. This means that it often is faster than the comparison-based sort algorithms, who often have a complexity of O(n log n).

Description of the LSD radix sorting algorithm

Lets say that we have an array with the following integer values: [132, 534, 612, 774, 599]. The algorithm starts by examining all the values at the least significant position. All the keys with the same value on that position will be grouped together. We have 10 groups, one for each integer value. In the C# code example below we refer to each group as a "bucket".

After this first round we would have the following grouping:

Group   Keys
0
1
2            132, 612
3
4            534, 774
5
6
7
8
9            599

In the next round LSD radix sort will check the next position and group by that value. Since it is a stable algorithm it will retain the relative position of elements set by the previous pass.

After the second round we will have this grouping:

Group   Keys
0
1            612
2          
3            132, 534
4          
5
6
7            774
8
9            599


In this case all keys consist of 3 digits, so next round will be the last one. It will now check the third value, which in this case is the most significant digit and group by that.

Again we keep the previous relative ordering and get the following:

Group   Keys
0
1            132    
2          
3          
4          
5            534, 599
6            612
7            774
8
9

So after three rounds we now have an ordered collection and the sorting is finished.

Example of an implementation of radix sort in C#

    private void SortArrayWithRadixSort()
    {
        int[] array = { 7, 5, 3, 6, 76, 45, 32 };
        int[] sortedArray = RadixSort(array);

        // PrintResult(sortedArray);
    }
    
    public int[] RadixSort(int[] array)
    {
        bool isFinished = false;
        int digitPosition = 0;

        List<Queue<int>> buckets = new List<Queue<int>>();
        InitializeBuckets(buckets);

        while (!isFinished)
        {
            isFinished = true;

            foreach (int value in array)
            {
                int bucketNumber = GetBucketNumber(value, digitPosition);
                if (bucketNumber > 0)
                {
                    isFinished = false;
                }

                buckets[bucketNumber].Enqueue(value);
            }

            int i = 0;
            foreach (Queue<int> bucket in buckets)
            {
                while (bucket.Count > 0)
                {
                    array[i] = bucket.Dequeue();
                    i++;
                }
            }

            digitPosition++;
        }

        return array;
    }

    private int GetBucketNumber(int value, int digitPosition)
    {
        int bucketNumber = (value / (int)Math.Pow(10, digitPosition)) % 10;
        return bucketNumber;
    }

    private static void InitializeBuckets(List<Queue<int>> buckets)
    {
        for (int i = 0; i < 10; i++)
        {
            Queue<int> q = new Queue<int>();
            buckets.Add(q);
        }
    }