ZetCode

C# Radix Sort

last modified November 6, 2026

In this article we implement the radix sort algorithm in C#. We sort integers digit by digit, sort fixed-length string codes, and write a fast byte-wise version that handles negative numbers.

Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.

Radix sort algorithm

Radix sort does not compare elements. It sorts the keys one digit at a time. The least significant digit (LSD) variant starts with the last digit and ends with the first one. Each pass uses a stable counting sort on a single digit. Because the passes are stable, the order from the previous digits is kept for elements with the same current digit.

PropertyValue
TimeO(d(n + b)), for d digits in base b
Extra memoryO(n + b)
Stableyes

The radix is the base of the digits. Base 10 is easy to follow, but computers prefer base 256, where a digit is one byte of the key.

C# radix sort example

The first example sorts non-negative integers by their decimal digits.

Program.cs 
int[] nums = [170, 45, 75, 90, 802, 24, 2, 66];

RadixSort(nums);
Console.WriteLine(string.Join(" ", nums));

static void RadixSort(int[] arr)
{
    int max = arr.Max();
    int[] output = new int[arr.Length];

    for (int exp = 1; max / exp > 0; exp *= 10)
    {
        int[] counts = new int[10];

        foreach (int x in arr)
        {
            counts[x / exp % 10]++;
        }

        for (int d = 1; d < 10; d++)
        {
            counts[d] += counts[d - 1];
        }

        for (int i = arr.Length - 1; i >= 0; i--)
        {
            int d = arr[i] / exp % 10;
            output[--counts[d]] = arr[i];
        }

        output.CopyTo(arr, 0);
    }
}

The number of passes is given by the number of digits of the largest element. 

for (int exp = 1; max / exp > 0; exp *= 10)

The exp variable is 1, 10, 100, and so on. The loop ends when exp is greater than the maximum. 

counts[x / exp % 10]++;

The expression x / exp % 10 extracts the current digit. We count the occurrences of each digit. 

for (int i = arr.Length - 1; i >= 0; i--)
{
    int d = arr[i] / exp % 10;
    output[--counts[d]] = arr[i];
}

output.CopyTo(arr, 0);

After the prefix sums, the counts give the positions in the output. Placing the elements from the end keeps the pass stable. The output is copied back for the next pass. 

$ dotnet run
2 24 45 66 75 90 170 802

Radix sort step by step

The next example prints the array after each pass.

Program.cs 
int[] nums = [329, 457, 657, 839, 436, 720, 355];

int max = nums.Max();
int[] output = new int[nums.Length];

for (int exp = 1; max / exp > 0; exp *= 10)
{
    int[] counts = new int[10];

    foreach (int x in nums) counts[x / exp % 10]++;
    for (int d = 1; d < 10; d++) counts[d] += counts[d - 1];

    for (int i = nums.Length - 1; i >= 0; i--)
    {
        output[--counts[nums[i] / exp % 10]] = nums[i];
    }

    output.CopyTo(nums, 0);
    Console.WriteLine($"by digit {exp,3}: {string.Join(" ", nums)}");
}

The first pass sorts the numbers by the last digit: 720 ends with 0, 355 with 5. The second pass sorts by the tens; 720 and 329 both have 2, and they keep their order from the first pass. After the third pass, the array is sorted. 

$ dotnet run
by digit   1: 720 355 436 457 657 329 839
by digit  10: 720 329 436 839 355 457 657
by digit 100: 329 355 436 457 657 720 839

Sorting strings

LSD radix sort works for strings of the same length, such as codes or identifiers. Each character is a digit with 128 possible values for ASCII text.

Program.cs 
string[] codes = ["BX42", "AC17", "BX19", "ZA01", "AC09", "MK77", "AB42"];

RadixSort(codes);
Console.WriteLine(string.Join(" ", codes));

static void RadixSort(string[] arr)
{
    int width = arr[0].Length;
    string[] output = new string[arr.Length];

    for (int pos = width - 1; pos >= 0; pos--)
    {
        int[] counts = new int[128];

        foreach (string s in arr) counts[s[pos]]++;
        for (int c = 1; c < 128; c++) counts[c] += counts[c - 1];

        for (int i = arr.Length - 1; i >= 0; i--)
        {
            output[--counts[arr[i][pos]]] = arr[i];
        }

        output.CopyTo(arr, 0);
    }
}

We sort codes made of two letters and two digits. 

for (int pos = width - 1; pos >= 0; pos--)

The passes go from the last character to the first one. 

foreach (string s in arr) counts[s[pos]]++;

The character code is used directly as the index into the count array.

The result is the ordinal order. Strings of different lengths would need padding or the most significant digit variant, which starts with the first character. 

$ dotnet run
AB42 AC09 AC17 BX19 BX42 MK77 ZA01

Byte-wise radix sort

The last example sorts 32-bit integers in four passes over their bytes. It handles negative numbers and compares the speed with Array.Sort.

Program.cs 
#:property PublishAot=false

using System.Diagnostics;

int[] small = [5, -3, 1_000_000, -2_000_000_000, 0, 42, int.MaxValue, int.MinValue];
RadixSort(small);
Console.WriteLine(string.Join(" ", small));

var rnd = new Random(17);
int[] data = [.. Enumerable.Range(0, 10_000_000).Select(_ => rnd.Next(int.MinValue, int.MaxValue))];

int[] a = [.. data];
var sw = Stopwatch.StartNew();
RadixSort(a);
Console.WriteLine($"Radix sort: {sw.ElapsedMilliseconds} ms");

int[] b = [.. data];
sw.Restart();
Array.Sort(b);
Console.WriteLine($"Array.Sort: {sw.ElapsedMilliseconds} ms");

Console.WriteLine($"Same result: {a.SequenceEqual(b)}");

static void RadixSort(int[] arr)
{
    int[] buffer = new int[arr.Length];
    int[] src = arr, dst = buffer;
    int[] counts = new int[256];

    for (int shift = 0; shift < 32; shift += 8)
    {
        Array.Clear(counts);

        foreach (int x in src) counts[Digit(x, shift)]++;

        int total = 0;
        for (int d = 0; d < 256; d++)
        {
            int c = counts[d];
            counts[d] = total;
            total += c;
        }

        foreach (int x in src) dst[counts[Digit(x, shift)]++] = x;

        (src, dst) = (dst, src);
    }
}

static int Digit(int x, int shift) => (int)(((uint)x ^ 0x8000_0000u) >> shift) & 0xFF;

First we check the order with a few extreme values, then we sort ten million random integers. 

static int Digit(int x, int shift) => (int)(((uint)x ^ 0x8000_0000u) >> shift) & 0xFF;

In two's complement, negative numbers have the highest bit set, so as unsigned numbers they would come after the positive ones. Flipping the sign bit maps int.MinValue to 0 and int.MaxValue to uint.MaxValue, which gives the correct order. The shift and the mask then extract one byte. 

int total = 0;
for (int d = 0; d < 256; d++)
{
    int c = counts[d];
    counts[d] = total;
    total += c;
}

foreach (int x in src) dst[counts[Digit(x, shift)]++] = x;

This time we compute the starting position of each digit, an exclusive prefix sum. The elements are then placed in a forward pass, which is also stable. 

(src, dst) = (dst, src);

Instead of copying, the two arrays swap their roles after each pass. After four passes, the data is back in the input array. 

#:property PublishAot=false

File-based apps are published with Native AOT by default. The directive turns this off, so the release build does not pull in the AOT compiler package.

We run the program in the Release configuration. Radix sort needs four linear passes regardless of the values and is several times faster than Array.Sort for this data. The price is a second array of the same size. 

$ dotnet run -c Release benchmark.cs
-2147483648 -2000000000 -3 0 5 42 1000000 2147483647
Radix sort: 85 ms
Array.Sort: 738 ms
Same result: True

Source

Bitwise and shift operators

In this article we have implemented the radix sort algorithm in C#.

Other sorting algorithms in C#:

Author

My name is Jan Bodnar and I am a passionate programmer with many years of programming experience. I have been writing programming articles since 2007.

So far, I have written over 1400 articles and 8 e-books. I have over eight years of experience in teaching programming.

List all C# tutorials.