Updated on
Radix sort orders numbers one digit at a time, from the least significant digit to the most significant, without comparing the numbers with each other. Our C# version loops over the digits and runs a counting sort for each one.
If you’re a programmer, you’ve probably heard of radix sort. But how do we use it in our code, and when is it fast? We’ll implement it, work out its time and space complexity, and measure it against Array.Sort().
Let’s dive in.
What Is Radix Sort?
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.
The NIST Dictionary of Algorithms and Data Structures defines it as a multiple-pass algorithm that “distributes each item to a bucket according to part of the item’s key”. In our code, the buckets are the ten possible digits, 0 to 9, and the part of the key is the current digit.
Besides that, it is a non-comparative sorting algorithm, meaning that it does not compare the values of the numbers to decide their order. 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.Â
How Does the Radix Sort Algorithm Work?
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
Look at the numbers that share a digit. After the first pass, 1 comes before 21 because it came first in the original array. The second pass keeps 1 before 8 because the first pass put it there. Every pass keeps the order the previous pass left for equal digits, and that is why the last pass leaves the whole array sorted.
Let’s learn how to implement the radix sort algorithm in C#.
How to Implement Radix Sort in C#?
To implement radix sort in C#, we need three small methods. One finds the largest value, one runs a counting sort on a single digit, and RadixSort() ties them together.
The largest value decides how many passes we make. A number with five digits needs five passes: one for the ones, one for the tens, and so on up to the ten thousands.
On each pass, the counting sort reads one digit of every number with (array[i] / exponent) % 10. It counts how many numbers have each digit from 0 to 9, turns those counts into end positions, and copies every number into a temporary array at its position.
It walks the array from the back while it copies. Numbers with the same digit keep the order the previous pass gave them, so the result is correct after the last pass.
The method sorts the array we pass in and returns that same array.
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, in a RadixSortMethods class of a new console app, 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() in the same class that takes an array and its size as inputs and returns a sorted array:
public int[] RadixSort(int[] array, int size)
{
if (size == 0)
return array;
var maxVal = GetMaxVal(array, size);
for (long 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 position of the current digit, counting from 0. We iterate through the exponents until we reach the largest exponent, which we determine from maxVal.
An empty array has no largest value, so the method returns it right away. Without that check, GetMaxVal() would read array[0] and throw an IndexOutOfRangeException.
We also declare exponent as a long on purpose. With an int, an array that contains int.MaxValue makes exponent *= 10 overflow after 1,000,000,000. The loop then runs two extra passes with meaningless exponents before it stops, 12 passes instead of 10. The array still ends up sorted, but the method does 20% more work than it needs.
Next, we are going to pass array, size and exponent as inputs to CountingSort(), which goes in the same class:
public static void CountingSort(int[] array, int size, long exponent)
{
var outputArr = new int[size];
var occurrences = new int[10];
for (int i = 0; i < size; i++)
occurrences[(array[i] / exponent) % 10]++;
for (int i = 1; i < 10; i++)
occurrences[i] += occurrences[i - 1];
for (int i = size - 1; i >= 0; i--)
{
outputArr[occurrences[(array[i] / exponent) % 10] - 1] = array[i];
occurrences[(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 occurrences = new int[10];
C# fills a new int array with zeros, so occurrences starts with a count of zero for every digit. The next step is to determine the count of the occurrences of each digit, which we calculate using the current exponent:
for (int i = 0; i < size; i++)
occurrences[(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++)
occurrences[i] += occurrences[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[occurrences[(array[i] / exponent) % 10] - 1] = array[i];
occurrences[(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, in a test method of an MSTest project that references our app, 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 RadixSortMethods();
var sortedArray = sortFunction.RadixSort(array, array.Length);
Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(expected, sortedArray);
How Do We Sort Negative Numbers With Radix Sort?
Our RadixSort() method works only with numbers that are zero or larger. For a number like -3, (array[i] / exponent) % 10 gives the digit -3, and the method throws an IndexOutOfRangeException when it uses that digit as an index. It can also fail without any error: when every number is negative, the largest value is below zero, the loop makes no pass at all, and { -1, -2, -3 } comes back unchanged.
The simplest fix is to shift every number up by the smallest value, so the smallest becomes zero, then sort and shift them back. Let’s add a RadixSortWithNegatives() method to the same class:
public int[] RadixSortWithNegatives(int[] array, int size)
{
if (size == 0)
return array;
var minVal = GetMinVal(array, size);
if (minVal >= 0)
return RadixSort(array, size);
for (int i = 0; i < size; i++)
array[i] = checked(array[i] - minVal);
RadixSort(array, size);
for (int i = 0; i < size; i++)
array[i] += minVal;
return array;
}
GetMinVal(), which goes in the same class, is a copy of GetMaxVal() with the comparison flipped. When the smallest value is zero or larger, we call RadixSort() directly. Otherwise, we subtract it from every element, sort, and add it back. Moving every number by the same amount doesn’t change their order.
The shift has one limit. The largest value minus the smallest has to fit in an int, so an array that holds both int.MinValue and int.MaxValue can’t be shifted. The checked keyword turns that case into an OverflowException. Without it, the subtraction would wrap around silently, and the method could either throw or return the numbers in the wrong order.
What Is the Time and Space Complexity of Radix Sort?
Radix sort runs in O(d × (n + b)) time and needs O(n + b) extra space. Here n is the number of elements, d is the number of digits in the largest value, and b is the base, which is 10 in our code.
Each of the d passes is one counting sort. It reads every element a few times and walks the ten counters once, which gives the n + b part.
The order of the input does not change that work. A random array and a sorted array with the same largest value take the same number of passes, so the best, average and worst cases are the same for a given d. What changes the time is how many digits the largest value has.
The extra space is the output array that each pass allocates, plus the ten counters.
Radix sort is stable, and it does not sort in place.
Best-Case Time Complexity
Radix sort does the same work whatever order the elements come in, so a sorted array is not a best case. The best case comes from small values: when the largest number has d digits, the algorithm makes d passes.
Therefore, the algorithm has a best-case time complexity of O(d*(n + b)), where d is the number of digits in the largest number, n is the number of elements in the array, and b is the base. With one-digit numbers, that is a single pass.
Average-Case Time Complexity
Because the order doesn’t matter, the average case equals the best case for the same largest value. Our benchmark below shows it: random and sorted arrays of 20,000 numbers with a five-digit maximum take about the same time.
Therefore, the radix sort algorithm has an average-case time complexity of O(d*(n + b)).
Worst-Case Time Complexity
The worst case comes from one large value. If every element has five digits except one int.MaxValue, which has ten, the algorithm makes ten passes over the whole array instead of five.
In general, d is ⌊logb(mx)⌋ + 1, where mx is the largest value. Therefore, we can conclude that radix sort has a worst-case time complexity of O(logb(mx)(n+b)). For int values, d can’t be more than 10, so the time still grows linearly with n.
Advantages of Radix Sort Algorithm
The radix sort algorithm is fast when the array elements have few digits, because the largest value decides how many passes it makes.
It is ideal for use in suffix-array construction algorithms such as the DC3 algorithm.
It is stable (maintains the original order of elements with equal values) unlike other sorting algorithms such as quicksort. Our counting sort keeps it stable by filling the output array from the back.
Disadvantages of Radix Sort Algorithm
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, our base-10 version is slower than the built-in Array.Sort(). In the benchmark below, it takes about 1.6 times as long on 20,000 random numbers. Array.Sort() uses introsort, a mix of quicksort, heapsort and insertion sort that our quicksort article explains.
Performance Tests
Let’s assess how radix sort performs by measuring, with BenchmarkDotNet, the time it takes 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 in our RadixSortMethods class to generate a set of random array elements:
public static int[] CreateRandomArray(int size, int lower, int upper)
{
var array = new int[size];
for (int i = 0; i < size; i++)
array[i] = Random.Shared.Next(lower, upper);
return array;
}
The CreateRandomArray() method takes three integers size, lower and upper. Using the shared Random.Shared instance, 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 in the same class that generates a sequence of elements. This method gives us sorted input, so we can check whether the order of the elements changes anything for the average-case time complexity:
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 int.MaxValue, in one more method of the same class:Â
public static int[] CreateImbalancedArray(int[] array)
{
List<int> numbers = [.. array, int.MaxValue];
return numbers.ToArray();
}
RadixSort() writes its result back into the array we pass, and a benchmark method runs many times in a row. Reuse one array, and every call after the first gets the sorted output of the call before it.
So, we create each input once and copy it before every call. We also add Array.Sort() as a reference point:
public class RadixSortBenchmarks
{
private readonly RadixSortMethods _radix = new();
private int[] _source = [];
private int[] _work = [];
[Params("Random", "Sorted", "Imbalanced")]
public string Input { get; set; } = "Random";
[GlobalSetup]
public void Setup()
{
_source = Input switch
{
"Sorted" => RadixSortMethods.CreateSortedArray(20000),
"Imbalanced" => RadixSortMethods.CreateImbalancedArray(
RadixSortMethods.CreateRandomArray(19999, 10000, 30000)),
_ => RadixSortMethods.CreateRandomArray(20000, 10000, 30000)
};
_work = new int[_source.Length];
}
[Benchmark(Baseline = true)]
public int[] RadixSort()
{
_source.CopyTo(_work, 0);
return _radix.RadixSort(_work, _work.Length);
}
[Benchmark]
public int[] ArraySort()
{
_source.CopyTo(_work, 0);
Array.Sort(_work);
return _work;
}
}
Setup() runs once for each benchmark method and each Input value, before the timed calls. Random numbers between 10,000 and 30,000 have five digits, and so does the largest number in the sorted array, 19,999. The imbalanced array has 19,999 five-digit numbers from the same range plus one int.MaxValue. The copy costs O(n) time in both methods, so it does not change which one is faster.
The class goes in its own file in our console app. We add the BenchmarkDotNet package to the app, start the class file with using BenchmarkDotNet.Attributes;, and call BenchmarkRunner.Run<RadixSortBenchmarks>(); from its Program.cs, after using BenchmarkDotNet.Running;. Let’s run it in Release mode and look at the results:
| Method | Input | Mean | Error | StdDev | Ratio | |---------- |----------- |-----------:|---------:|---------:|------:| | RadixSort | Imbalanced | 2,450.8 us | 13.51 us | 12.64 us | 1.00 | | ArraySort | Imbalanced | 862.9 us | 4.37 us | 3.87 us | 0.35 | | | | | | | | | RadixSort | Random | 1,357.4 us | 4.78 us | 4.24 us | 1.00 | | ArraySort | Random | 854.2 us | 6.61 us | 6.18 us | 0.63 | | | | | | | | | RadixSort | Sorted | 1,329.5 us | 8.09 us | 6.76 us | 1.00 | | ArraySort | Sorted | 116.1 us | 1.00 us | 0.89 us | 0.09 |
Radix sort takes about the same time on random and on sorted numbers, around 1.3 to 1.4 milliseconds. Both arrays have a five-digit maximum, so both need five passes, and the order of the numbers doesn’t matter.
One int.MaxValue at the end of the array changes that. The largest value now has ten digits, the algorithm makes ten passes instead of five, and the time grows about 1.8 times.
Array.Sort() is faster in every row. On random numbers, it needs about 60% of radix sort’s time. On sorted numbers it is more than ten times faster, because Array.Sort() handles input that is already in order very cheaply.
So, our base-10 radix sort is good for learning how the algorithm works, while Array.Sort() is the faster choice for production code. Faster radix sorts work on bytes instead of decimal digits: four passes for any int, with shifts and masks instead of division. Please note that these runtimes may change depending on the number of elements and the computing resources available.
Conclusion
In this article, we have learned how radix sort in C# works and its time and space complexity.
Radix sort’s time depends on how many digits the largest number has, not on the order of the numbers, and it keeps equal values in their original order. Our base-10 version still loses to Array.Sort(), so that is the method to call in production. If you want to go further, bucket sort is another way to sort numbers by distributing them into buckets.
Tested with .NET 10.0.10, BenchmarkDotNet 0.15.8 and MSTest 4.5.2.
