## Introduction

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:

- Least significant digit (LSD) radix sort
- 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];
int[] SortedArray = new int[array.Length];
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:

Key | Value | Number |

3 | 2 | 252 |

1 | 5 | 505 |

4 | 5 | 75 |

2 | 6 | 146 |

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:

Key | Value | Number |

1 | 0 | 505 |

2 | 4 | 146 |

4 | 7 | 75 |

3 | 5 | 252 |

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:

Key | Value | Number |

4 | 0 | 75 |

2 | 1 | 146 |

3 | 2 | 252 |

1 | 5 | 505 |

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++)
ArrayB[ArrayA[i].Value]++;
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];
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:

#### ArrayA

Key | 1 | 2 | 3 | 4 |

Value | 5 | 6 | 2 | 5 |

#### ArrayB

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:

#### ArrayB

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`

:

#### 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
{
get
{
return key;
}
set
{
if (key >= 0)
key = value;
else
throw new Exception("Invalid key value");
}
}
public int Value
{
get
{
return value;
}
set
{
this.value = value;
}
}
}