Radix Sort Algorithm in DSA C#

Mental Model

Radix sort sorts numbers by processing digits from least significant to most significant, grouping numbers by each digit step by step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until all mail is sorted perfectly.

Array: [170, 45, 75, 90, 802, 24, 2, 66]
Buckets for digit 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

Input: list: [170, 45, 75, 90, 802, 24, 2, 66]

Goal: Sort the list in ascending order using radix sort by processing digits from least significant to most significant

Step 1: Sort numbers by least significant digit (units place)

Buckets:
0: [170, 90]
1: []
2: [802, 2]
3: []
4: [24]
5: [45, 75]
6: [66]
7: []
8: []
9: []
Reassembled array: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Grouping by units digit organizes numbers partially to prepare for next digit sorting

Step 2: Sort numbers by second least significant digit (tens place)

Buckets:
0: [802, 2]
1: []
2: [24]
3: []
4: []
5: [45]
6: [66]
7: [170, 75]
8: []
9: [90]
Reassembled array: [802, 2, 24, 45, 66, 170, 75, 90]

Why: Sorting by tens digit refines order further, grouping numbers by their tens place

Step 3: Sort numbers by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
2: []
3: []
4: []
5: []
6: []
7: []
8: [802]
9: []
Reassembled array: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Sorting by hundreds digit completes the sorting process for all numbers

Result:

Sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class RadixSort {
    // Function to get the maximum value in the array
    static int GetMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.Length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    // Counting sort based on digit represented by exp
    static void CountingSort(int[] arr, int exp) {
        int n = arr.Length;
        int[] output = new int[n]; // output array
        int[] count = new int[10]; // count array for digits 0-9

        // Count occurrences of digits
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // Change count[i] so that it contains actual position of this digit in output
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array from right to left to maintain stability
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // Copy output to arr
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    // Main radix sort function
    public static void RadixSortAlgorithm(int[] arr) {
        int max = GetMax(arr); // Find max to know number of digits

        // Do counting sort for every digit
        for (int exp = 1; max / exp > 0; exp *= 10) {
            CountingSort(arr, exp);
        }
    }

    // Helper to print array
    public static void PrintArray(int[] arr) {
        Console.WriteLine(string.Join(", ", arr));
    }

    static void Main() {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        Console.WriteLine("Original array:");
        PrintArray(arr);

        RadixSortAlgorithm(arr);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }
}

for (int i = 0; i < n; i++) { int digit = (arr[i] / exp) % 10; count[digit]++; }

count occurrences of current digit for all numbers

for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; }

transform count to positions for stable sorting

for (int i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; }

build output array from right to left to keep order stable

for (int i = 0; i < n; i++) { arr[i] = output[i]; }

copy sorted output back to original array

for (int exp = 1; max / exp > 0; exp *= 10) { CountingSort(arr, exp); }

repeat counting sort for each digit place from least to most significant

Output

Original array:

170, 45, 75, 90, 802, 24, 2, 66

Sorted array:

2, 24, 45, 66, 75, 90, 170, 802

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k=10 digits; because we do counting sort d times

Space: O(n + k) for output and count arrays used in counting sort

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit length numbers because it sorts by digits without comparisons

Edge Cases

Empty array

No sorting needed, function exits quickly

DSA C#

int max = GetMax(arr); // assumes arr has at least one element

Array with one element

Array remains unchanged, sorting steps run but no effect

DSA C#

for (int exp = 1; max / exp > 0; exp *= 10) { CountingSort(arr, exp); }

Array with all elements the same

Sorting steps run but array remains unchanged

DSA C#

CountingSort function handles stable sorting even if all digits are same

When to Use This Pattern

When you need to sort integers or fixed-length strings efficiently without comparisons, especially when digit length is small, use radix sort to leverage digit-by-digit grouping.

Common Mistakes

Mistake: Not maintaining stability in counting sort step, causing incorrect final order
Fix: Build output array from right to left to keep relative order of equal digits

Mistake: Forgetting to update the original array after counting sort
Fix: Copy the output array back to the original array after each digit sort

Mistake: Not handling the maximum digit length correctly, causing incomplete sorting
Fix: Use max value to determine number of digit passes with condition max / exp > 0

Summary

Radix sort sorts numbers by processing each digit from least to most significant using stable counting sort.

Use it when sorting integers or fixed-length digit strings efficiently without comparisons.

The key insight is sorting by each digit step-by-step preserves order and leads to fully sorted array.

Practice

1. What is the main idea behind the Radix Sort Algorithm?

easy

A. Sort numbers digit by digit starting from the least significant digit

B. Sort numbers by comparing each pair directly

C. Sort numbers by dividing them into two halves recursively

D. Sort numbers by swapping adjacent elements repeatedly

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing each digit separately, starting from the least significant digit (rightmost).

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, Radix Sort uses digit positions to sort without direct comparisons between whole numbers.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option A

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Radix Sort processes digits from right to left [OK]

Common Mistakes:

• Thinking Radix Sort compares whole numbers directly
• Confusing Radix Sort with quicksort or mergesort
• Assuming it sorts from most significant digit first

2. Which of the following is the correct way to initialize a queue in C# for use in Radix Sort?

easy

A. Queue<int> buckets = new Queue<int>[10];

B. Queue<int> buckets = new Queue<int>(10);

C. Queue buckets = new Queue<int>(10);

D. Queue<int>[] buckets = new Queue<int>[10];

Solution

1. Step 1: Understand array of queues declaration

   We need an array of 10 queues, so the correct syntax is an array of Queue<int>: Queue<int>[] buckets = new Queue<int>[10];

2. Step 2: Check other options

   Queue<int> buckets = new Queue<int>[10]; tries to assign an array to a single Queue<int> variable, which is invalid. Queue buckets = new Queue<int>(10); uses non-generic Queue incorrectly. Queue<int> buckets = new Queue<int>(10); creates a single Queue with capacity 10, not an array.

3. Final Answer:

   Queue<int>[] buckets = new Queue<int>[10]; -> Option D

4. Quick Check:

   Array of queues = Queue<int>[] [OK]

Hint: Use [] to declare array of queues in C# [OK]

Common Mistakes:

• Declaring a single queue instead of an array
• Using non-generic Queue instead of Queue<int>
• Confusing array initialization syntax

3. What will be the output of the following C# code snippet using Radix Sort on the array [170, 45, 75, 90, 802, 24, 2, 66]?

int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
RadixSort(arr);
Console.WriteLine(string.Join(", ", arr));

medium

A. [170, 45, 75, 90, 802, 24, 2, 66]

B. [2, 24, 45, 66, 75, 90, 170, 802]

C. [802, 170, 90, 75, 66, 45, 24, 2]

D. [24, 2, 45, 66, 75, 90, 170, 802]

Solution

1. Step 1: Apply Radix Sort on given array

   Radix Sort sorts numbers by digits from least significant to most significant. After sorting, the array becomes sorted in ascending order: 2, 24, 45, 66, 75, 90, 170, 802.

2. Step 2: Verify output matches sorted array

   [2, 24, 45, 66, 75, 90, 170, 802] matches the sorted array. [170, 45, 75, 90, 802, 24, 2, 66] is original unsorted. [802, 170, 90, 75, 66, 45, 24, 2] is descending order. [24, 2, 45, 66, 75, 90, 170, 802] is incorrect order.

3. Final Answer:

   [2, 24, 45, 66, 75, 90, 170, 802] -> Option B

4. Quick Check:

   Radix Sort output = Sorted array ascending [OK]

Hint: Radix Sort outputs sorted array ascending [OK]

Common Mistakes:

• Confusing original and sorted array
• Assuming Radix Sort sorts descending
• Mixing digit order in sorting

4. Identify the error in this Radix Sort code snippet in C#:

for (int i = 0; i < maxDigit; i++)
{
    Queue<int>[] buckets = new Queue<int>[10];
    for (int j = 0; j < 10; j++)
        buckets[j] = new Queue<int>();

    foreach (int num in arr)
    {
        int digit = (num / (int)Math.Pow(10, i)) % 10;
        buckets[digit].Enqueue(num);
    }

    int index = 0;
    foreach (var bucket in buckets)
    {
        while (bucket.Count > 0)
            arr[index++] = bucket.Dequeue();
    }
}

medium

A. The inner foreach loop should use a for loop instead

B. The digit calculation is incorrect; it should use modulus 100

C. There is no error in the code snippet

D. The buckets array is reinitialized inside the outer loop, causing loss of data

Solution

1. Step 1: Analyze the code structure

   The code correctly creates fresh buckets for each digit position, distributes all elements by the current digit using stable queues, and reconstructs the array in place. This is proper LSD Radix Sort implementation.

2. Step 2: Evaluate options

   A: foreach loops are fine for iterating arr and buckets. B: (num / pow(10,i)) % 10 correctly extracts the i-th digit from LSD. C: Reinitializing buckets each pass prevents carry-over from previous passes and does not lose data since all elements are re-enqueued from arr every iteration.

3. Final Answer:

   There is no error in the code snippet -> Option C

4. Quick Check:

   Buckets reinitialized each pass = Correct [OK]

Hint: Buckets reset each digit pass is required, not an error [OK]

Common Mistakes:

• Thinking buckets reinitialization causes data loss
• Misunderstanding digit extraction formula
• Resetting index inside wrong loop

5. You want to adapt Radix Sort to sort an array of strings representing numbers with varying lengths (e.g., ["170", "45", "9", "802", "24"]). Which approach is best to handle different string lengths correctly?

hard

A. Pad shorter strings with leading zeros to match the longest length before sorting

B. Sort strings as they are without padding, digit by digit from left to right

C. Convert strings to integers and apply normal Radix Sort

D. Sort strings by length first, then apply Radix Sort on digits

Solution

1. Step 1: Understand problem with varying string lengths

   Radix Sort requires uniform digit positions. Strings of different lengths cause misalignment when sorting digit by digit.

2. Step 2: Choose padding strategy

   Padding shorter strings with leading zeros makes all strings equal length, allowing digit-by-digit sorting from right to left correctly.

3. Step 3: Evaluate other options

   Sort strings as they are without padding, digit by digit from left to right sorts left to right which breaks Radix Sort logic. Convert strings to integers and apply normal Radix Sort loses string format and may cause overflow. Sort strings by length first, then apply Radix Sort on digits sorting by length first does not solve digit alignment.

4. Final Answer:

   Pad shorter strings with leading zeros to match the longest length before sorting -> Option A

5. Quick Check:

   Pad strings to equal length = Correct approach [OK]

Hint: Pad strings with zeros to equal length before sorting [OK]

Common Mistakes:

• Sorting strings without padding causes wrong order
• Sorting digits left to right breaks Radix Sort
• Converting strings to int may cause errors with large numbers