C# ## Radix Sort in C#

If you’re a programmer, you’ve probably heard of the radix sort. But what is it, exactly? And how can you use it in your code? In this article, we’ll take a closer look at the radix sort in C#, learn how to implement it, and analyze its time and space complexity.

To download the source code for this article, you can visit our GitHub repository.

Let’s dive in.

**Radix sort is an efficient sorting algorithm that sorts numbers by checking their digits one at a time**, starting with the least significant digit and moving to the most significant digit.

Besides that, **it is a non-comparative sorting algorithm**, meaning that it does not compare the values of the numbers being sorted. However, it uses counting sort as its “inner algorithm” to perform the sorting process.

Let’s take a deep dive and learn how radix sort works.

Let’s look at an example of how radix sort works. We will use the following set of numbers:

`int[] array = {110, 1, 21, 53, 8, 98, 26, 163, 38, 897};`

The algorithm starts sorting the elements by first checking the least significant digit. After sorting the array based on the one’s place digit, the array becomes:

`110, 1, 21, 53, 163, 26, 897, 8, 98, 38`

Next, we are going to sort the array based on its ten’s place digit, which yields this result:

`01, 08, 110, 21, 26, 38, 53, 163, 897, 98`

Since **897** is our largest number, the iteration stops after checking the hundred’s place digit:

`001, 008, 021, 026, 038, 053, 098, 110, 163, 897`

Let’s learn how to implement the radix sort algorithm in C#.

Since radix sort is not a comparative algorithm, we have to check the number of digits that the largest number in the array has. Therefore, let’s write a `GetMaxVal()`

method that takes an array and its size as inputs and returns the largest integer in that array:

public static int GetMaxVal(int[] array, int size) { var maxVal = array[0]; for (int i = 1; i < size; i++) if (array[i] > maxVal) maxVal = array[i]; return maxVal; }

The `GetMaxVal()`

method iterates through the array from the first element to the last one while updating the value of `maxVal`

, which we are going to need as we implement the radix sort algorithm.

Next, we are going to write a method `RadixSort()`

that takes an array and its size as inputs and returns a sorted array:

public int[] RadixSort (int[] array, int size) { var maxVal = GetMaxVal(array, size); for (int exponent = 1; maxVal / exponent > 0; exponent *= 10) CountingSort(array, size, exponent); return array; }

We can see that the process starts by getting the largest integer in the array by invoking `GetMaxVal()`

. Once we get the largest integer in the array, we invoke the counting sort method for every exponent.

`exponent`

is calculated as **10^i** where **i** is the current digit. We iterate through the exponents until we reach the largest exponent, which we determine from `maxVal`

.

Next, we are going to pass `array`

, `size`

and `exponent`

as inputs to `CountingSort()`

:

public static void CountingSort(int[] array, int size, int exponent) { var outputArr = new int[size]; var occurences = new int[10]; for (int i = 0; i < 10; i++) occurences[i] = 0; for (int i = 0; i < size; i++) occurences[(array[i] / exponent) % 10]++; for (int i = 1; i < 10; i++) occurences[i] += occurences[i - 1]; for (int i = size - 1; i >= 0; i--) { outputArr[occurences[(array[i] / exponent) % 10] - 1] = array[i]; occurences[(array[i] / exponent) % 10]--; } for (int i = 0; i < size; i++) array[i] = outputArr[i]; }

Let’s understand how the `CountingSort()`

method works:

First, we define and initialize two arrays `outputArr`

and `occurrences`

, which are going to come in handy during the sorting process:

var outputArr = new int[size]; var occurences = new int[10]; for (int i = 0; i < 10; i++) occurences[i] = 0;

We set all the elements in `occurrences`

to zero as we prepare to update it when we start the sorting process. The next step is to determine the count of the occurrences of each array element, which we calculate using the current exponent:

for (int i = 0; i < size; i++) occurences[(array[i] / exponent) % 10]++;

Now, we change `occurrences[i]`

in such a manner that `occurrences[i]`

now stores the actual position of the digit in the `outputArr`

:

for (int i = 1; i < 10; i++) occurences[i] += occurences[i - 1];

Once we have these array positions stored in `occurrences`

, we can now set the elements based on their sorted positions as we add them to `outputArr`

:

for (int i = size - 1; i >= 0; i--) { outputArr[occurences[(array[i] / exponent) % 10] - 1] = array[i]; occurences[(array[i] / exponent) % 10]--; }

We can now copy the elements in `outputArr`

over to `array`

to complete the sorting process:

for (int i = 0; i < size; i++) array[i] = outputArr[i];

Finally, we can verify that the `RadixSort()`

method sorts a given unsorted array accurately:

var array = new int[] { 73, 57, 49, 99, 133, 20, 1 }; var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 }; var sortFunction = new InsertionSortMethods(); var sortedArray = sortFunction.SortArray(array, array.Length); Assert.IsNotNull(sortedArray); CollectionAssert.AreEqual(sortedArray, expected);

From our implementation, we can see that radix sort requires **O(n + k)** space with n being the number of elements and k being the space used to hold counts, indices, and output arrays. However, since k is constant, the space complexity of the algorithm is **O(n)**.

The best-case time complexity of radix sort occurs when all the elements in the array have the same number of digits.

Therefore, the algorithm has a best-case time complexity of **O(d*n)**, where d is the number of digits in the largest number and n is the number of elements in the array.

The radix sort algorithm encounters the average-case time complexity scenario when the array elements have digits that are distributed uniformly. Assuming we are going to make ‘p’ passes and each digit is going to have up to ‘d’ different values, we can compute the average time complexity of the radix sort algorithm to be **T(n) = p(n+d)** where n is the number of elements.

Therefore, the radix sort algorithm has an average-case time complexity of **O(p(n+d)).**

The radix sort algorithm encounters a worst-case time complexity scenario when all the array elements in the array have the same number of digits except one, which has a large number of digits. This means, assuming the largest element has n number of digits, the algorithm has a runtime of **O(n ^{2})**.

On the other hand, since we also use counting sort in our implementation, its worst-case runtime is **O(n+b)**, which can be summarized as **O(n)**. From our implementation, assuming we call counting sort d times with **d = [**

**O(log _{b}(mx)(n+b)).**

The radix sort algorithm is fast when the range of the array elements is minimal.

It is ideal for use in suffix-array construction algorithms such as Manber’s algorithm and DC3 algorithm.

It is stable (maintains the original order of elements with equal values) unlike other sorting algorithms such as quicksort.

Radix sort is a bit more complex to implement than other sorting algorithms such as selection and bubble sort.

It is less flexible than other sorting algorithms as it mostly depends on digits or letters. Therefore, we need to refactor it whenever we need to sort arrays of different data types.

Radix sort is not an in-place sorting algorithm since it requires additional space unlike algorithms such as quicksort, insertion sort, and bubble sort.

Finally, the algorithm can be slower than algorithms that use divide and conquer approaches such as merge sort and quicksort for large arrays.

Let’s assess how radix sort performs by measuring the time it takes for it to sort an array that has 20,000 elements. To help us complete these tests, we are going to implement three methods.

First, let’s write a method to generate a set of random array elements:

public static int[] CreateRandomArray(int size, int lower, int upper) { var array = new int[size]; var rand = new Random(); for (int i = 0; i < size; i++) array[i] = rand.Next(lower, upper); return array; }

The `CreateRandomArray()`

the method takes three integers `size`

, `lower`

and `upper`

. Using the inbuilt `Random`

class, we generate integer values between `lower`

and `upper`

that we’re going to put into the array.

Next, we are going to define a method that generates a sequence of elements. This method simulates an average-case time complexity scenario where the elements are distributed evenly across different digits:

public static int[] CreateSortedArray(int size) { var array = new int[size]; for (int i = 0; i < size; i++) array[i] = i; return array; }

To simulate the worst-case time complexity scenario, we are going to use the `CreateRandomArray()`

we have but add an element that has a lot of digits at the end of the array such as `Int32.MaxValue`

:

public static int[] CreateImbalancedArray(int[] array) { List<int> numbers = new List<int>(); numbers.AddRange(array); numbers.Add(Int32.MaxValue); return numbers.ToArray(); }

Next, we are going to create an object that holds different arrays that have random and sorted values:

public IEnumerable<object[]> SampleArrays() { yield return new object[] { CreateRandomArray(20000, 10000, 30000), 20000, "Best Case" }; yield return new object[] { CreateSortedArray(20000), 20000, "Average Case" }; yield return new object[] { CreateImbalancedArray(CreateRandomArray(19999, 10000, 30000)), 20000, "Worst Case" }; }

Each object entry has three values: an integer array e.g. `CreateRandomArray(20000, 10000, 30000)`

, its length (20,000), and a string object storing the name of that array (“Best Case”). This object sorts random numbers between 10,000 and 30,000, which have the same number of digits.

The `CreateSortedArray()`

the method creates arrays that have values that are sorted, which is ideal for simulating arrays whose values are uniformly distributed.

On the other hand, the last object invokes the `CreateImbalancedArray()`

which has elements that have elements with the same number of digits except `Int32.MaxValue`

.

Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:

| Method | array | size | arrayName | Mean | Error | StdDev | |---------- |------------- |------ |------------- |---------:|----------:|----------:| | RadixSort | Int32[20000] | 20000 | Average Case | 3.022 ms | 0.0873 ms | 0.2534 ms | | RadixSort | Int32[20000] | 20000 | Best Case | 2.961 ms | 0.0803 ms | 0.2341 ms | | RadixSort | Int32[20000] | 20000 | Worst Case | 7.785 ms | 0.3323 ms | 0.9798 ms |

As we can see, despite the algorithm handling the same number of elements, they have different runtimes, which demonstrates the different levels of time complexities encountered by the array.

The **worst-case time complexity’s runtime is about three times longer than the best-case time complexity’s runtime**. On the other hand, **the average-case runtime is about 1ms slower than the best-case runtime**. Please note that **these runtimes may change depending on the number of elements and the computing resources available. **

In this article, we have learned how radix sort in C# works and its time and space complexity.

Issue #141 of the Code Maze weekly. Check out what's new this week and enjoy…

Updated Date Sep 30, 2022

In this post, we are going to learn how to read AppSettings values from a…

Sep 28, 2022

In this article, we are going to learn how to count occurrences of a char…

Updated Date Sep 29, 2022

In this article, we are going to explore Shouldly. Shouldly is a library that improves…

Updated Date Sep 26, 2022

Issue #140 of the Code Maze weekly. Check out what's new this week and enjoy…

Updated Date Sep 23, 2022

In this article, we are going to explain how we can work with query string…

Updated Date Sep 22, 2022