Click here to Skip to main content
12,831,676 members (33,372 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


22 bookmarked
Posted 10 Jan 2009

Radix Sorting Implementation with C#

, 28 Feb 2009 CPOL
Rate this:
Please Sign up or sign in to vote.
Radix sorting implementation with C#


The article presented here is a description of the implementation of radix sort algorithm with C#.

Radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of digits, it can sort integers with Worst case performance O(K*N) where K is the number of digits and N is the number of integers being sorted.

There are two types of radix sorting:

  1. Least significant digit (LSD) radix sort
  2. Most significant digit (MSD) radix sort

LSD radix sorts process the integer representations starting from the least significant digit and move towards the most significant digit. MSD radix sorts work the other way around.

In this article, we will focus on the (LSD) radix sort.

Necessary Knowledge

A general knowledge of sorting algorithms is essential.

How the algorithm implementation works:

Let us assume that we have an array of integers like this {505,146,252,75}.

We assign each of them a key: (We will explain why we use keys later in the article.)


The algorithm is divided into two parts which are "Radix and counting algorithms". We will explain each of them separately:

1. Radix

The Code for the Radix Sorting Methods

public static int[] Sort(int[] array)
    return RadixSortAux(array, 1);
        static int[] RadixSortAux(int[] array, int digit)
            bool Empty = true;
            KVEntry[] digits = new KVEntry[array.Length];//array that holds the digits;
            int[] SortedArray = new int[array.Length];//Hold the sorted array
            for (int i = 0; i < array.Length; i++)
                digits[i] = new KVEntry();
                digits[i].Key = i;
                digits[i].Value = (array[i] / digit) % 10;
                if (array[i]/digit!=0)
                    Empty = false;

            if (Empty)
                return array;

            KVEntry[] SortedDigits = CountingSort(digits);
            for (int i = 0; i < SortedArray.Length; i++)
                SortedArray[i] = array[SortedDigits[i].Key];
            return RadixSortAux(SortedArray, digit * 10);

Let's look at the RadixSortAux method. It starts by taking all digits of all numbers from CountingSort method for sorting and sorting the numbers according to the digits arrangement.

Foreach iteration in RadixSortAux digit is multiplied by 10 so as to get the next digit, and we check foreach number if number/digit not equal to zero therefore there are more digits to sort. If not, this means that we have reached the end of the numbers.

a) Taking array of the unit digits of the array {5,6,2,5} let it be arrayA.

Start by assigning them keys :


b) Use the counting algorithm to sort them. I'll explain the counting algorithm later in the article. The digits array will be as follows:


Note that the counting algorithm is a stable algorithm so the two '5' values don't swap, stability is essential in the radix algorithm.

c) After sorting the array of digits, we sort their numbers according to their arrangement:


So, numbers now are sorted according to their least significant digit...

d) Now we take an array of the tenth digit {5,0,7,4} and make the same operation on it, so the numbers after being sorted will be as follows:


e) Now we just have one more step and the array will be sorted.:) We take an array of the hundredth digit {5,1,0,2} and sort the numbers according to the sorted array of hundredth digits:


Finally, the array is sorted now. We just have to know how the counting algorithm works for sorting the digits.

2. Counting Algorithm

static KVEntry[] CountingSort(KVEntry[] ArrayA)
    int[] ArrayB = new int[MaxValue(ArrayA) + 1];
    KVEntry[] ArrayC = new KVEntry[ArrayA.Length];

    for (int i = 0; i < ArrayB.Length; i++)
	ArrayB[i] = 0;

    for (int i = 0; i < ArrayA.Length; i++)

    for (int i = 1; i < ArrayB.Length; i++)
	ArrayB[i] += ArrayB[i - 1];

    for (int i = ArrayA.Length - 1; i >= 0; i--)
	int value = ArrayA[i].Value;
	int index = ArrayB[value];
	ArrayC[index - 1] = new KVEntry();
	ArrayC[index - 1].Key = i;
	ArrayC[index - 1].Value = value;
    return ArrayC;

static int MaxValue(KVEntry[] arr)
    int Max = arr[0].Value;
    for (int i = 1; i < arr.Length; i++)
        if (arr[i].Value > Max)
	   Max = arr[i].Value;
        return Max;

a) The counting algorithm creates another array of length 7 which is the (maximum number in arrayA) + 1 , then we add the number of recurrences foreach element of ArrayA in its index in ArrayB as follows:


Key 1 2 3 4
Value 5 6 2 5


Index 0 1 2 3 4 5 6
Value 0 0 1 0 0 2 1

The number of recurrences of 5 in ArrayA is put in ArrayB[5] which is 2, the number of recurrences of 6 in ArrayA is put in ArrayB[6] which is 1, and so on.

b) We start moving on ArrayB from ArrayB[1] to the end and increment each of them with the value in the index before:


Index 0 1 2 3 4 5 6
Value 0 0 1 1 1 3 4

c) Then we use a third array. Let it be ArrayC. This is the array in which integers will be put in sorted.

We start moving on all the integers in ArrayA from the right to the left: Let's say now we are on ArrayA[1], the value is 5, we now go to the index 5 in ArrayB and get its value. Now we get the index of value 5 in ArrayC which is equal to ArrayB[5] - 1. You can understand it from the following figure:

After this step, we should have a sorted array which is ArrayC:


Key 3 1 4 2
Value 2 5 5 6

Why We Use the Key/Value Pair

When sorting each digit for all numbers separately, we need to sort the numbers according to the digits arrangement so we assign them keys to sort the numbers:

The Numbers Array

Key 1 2 3 4
Value 505 146 252 75

Digits Array after Sorting which is ArrayC

Key 3 1 4 2
Value 2 5 5 6

So, by sorting the numbers array according to ArrayC, the arrangement of keys will be:

Key 3 1 4 2
Value 252 505 75 146
struct KVEntry
    int key;
    int value;

    public int Key
             return key;
	    if (key >= 0)
		key = value;
		throw new Exception("Invalid key value");

    public int Value
             return value;
	    this.value = value;


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Mostafa saeed
Software Developer Premium methods
Egypt Egypt
Student at Faculty of computer and information sciences at Ainshams University,I'm a programmer from three years ago working with

Programming languages :
Intel 8086 Assembly,C,C++,C#,VB,Visual prolog.

Web development languages and technologies:

Database engines:
Oracle,SQL Server and MySQL.

You may also be interested in...


Comments and Discussions

QuestionHow to use the code in sorting strings Pin
gamer11273-Sep-09 23:33
membergamer11273-Sep-09 23:33 
GeneralA better one Pin
tamash_ionut10-Jan-09 7:58
membertamash_ionut10-Jan-09 7:58 
GeneralRe: A better one Pin
afterburn2-Mar-09 18:45
memberafterburn2-Mar-09 18:45 
GeneralComplexity Pin
Georgi Atanasov10-Jan-09 6:23
memberGeorgi Atanasov10-Jan-09 6:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170326.1 | Last Updated 28 Feb 2009
Article Copyright 2009 by Mostafa saeed
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid