Radix Sort in Data Structure: Algorithm, Example & Time Complexity

Chapter 49 Data Structure / Sorting
Radix Sort in Data Structure: Algorithm, Example & Time Complexity

Understand digit-by-digit sorting, LSD and MSD Radix Sort, stable Counting Sort, complete dry run, C programming and algorithm performance with easy examples.

Non-Comparison Sorting LSD & MSD C Program Interactive Buckets Exam Notes
Digit Sorting Workshop
1 7 0
100s 10s 1s
Start from Ones

Suppose you have a list of roll numbers and want to arrange them from smallest to largest. In many sorting algorithms, we compare complete numbers with each other and decide which one should come first.

Radix Sort follows a different method. It does not primarily compare two complete numbers to decide their order. Instead, it processes the numbers according to their individual digits.

For example, the number 170 has three digits: 1 in the hundreds place, 7 in the tens place and 0 in the ones place.

By processing these digit positions carefully, Radix Sort can arrange the complete set of numbers.

Students often find this topic confusing because they mix up LSD and MSD, forget why stable sorting is important, or incorrectly assume that Radix Sort always takes O(n) time.

In this chapter, we will understand Radix Sort in Data Structure from the basic concept to a complete C program, using original examples, detailed calculations and exam-oriented notes.

Quick Answer: What Is Radix Sort?

Radix Sort is a non-comparison-based sorting algorithm that arranges keys by processing individual digits or characters. In LSD Radix Sort, digits are processed from the least significant position to the most significant position. A stable sorting method, such as Counting Sort, is used at each digit position to preserve the order established by previous passes.

01 / Basic Concept

What Is Radix Sort in Data Structure?

Radix Sort is a sorting technique that processes individual digit positions instead of repeatedly comparing entire numbers.

The word radix refers to the base of a number system.

For decimal numbers, the radix is 10 because the digits range from 0 to 9.

For binary numbers, the radix is 2 because only 0 and 1 are used.

Simple Radix Sort Example

Consider the values:

Original Array
45 12 31 24
↓ Process Ones Digit
31 12 24 45
↓ Process Tens Digit
12 24 31 45

Each digit pass uses stable sorting to preserve earlier order.

Important Features of Radix Sort

  • It processes digit positions or characters.
  • It does not rely on direct pairwise comparison of complete keys.
  • It can use stable Counting Sort for every digit pass.
  • It is useful when keys have a suitable finite digit representation.
  • Its complexity depends on the number of digits, elements and chosen radix.
  • A standard LSD implementation requires additional storage.

Memory Trick: LSD Radix Sort = Sort Ones → Sort Tens → Sort Hundreds → Continue.

02 / Place Value

Understanding Digit Positions in Radix Sort

Before learning the algorithm, we must understand how individual digits are extracted.

Take the number 802. It contains three decimal digit positions.

Place Value of 802
8 0 2

8 hundreds, 0 tens, 2 ones

Formula to Extract a Digit

To find a particular digit of a non-negative integer, we can use integer division and remainder.

digit = (number / place) % 10 place = 1 → Ones place = 10 → Tens place = 100 → Hundreds

Example: Extract Digits from 802

Ones: (802 / 1) % 10 = 2 Tens: (802 / 10) % 10 = 0 Hundreds: (802 / 100) % 10 = 8

What Happens to Smaller Numbers?

Suppose the number is 2. It does not have a written tens or hundreds digit.

During LSD sorting, missing higher digits are treated as zero.

2 → 002 24 → 024 170 → 170 802 → 802

These leading zeros are only used to understand digit positions. They do not change the number.

03 / Types of Radix Sort

LSD Radix Sort vs MSD Radix Sort

Radix Sort is commonly discussed in two major forms: LSD Radix Sort and MSD Radix Sort.

1. LSD Radix Sort

LSD stands for Least Significant Digit.

This approach begins with the rightmost digit. For decimal numbers, that is the ones position.

After sorting by ones, it processes tens, hundreds and any remaining higher positions.

Example: 472 Order of Processing: 2 → 7 → 4 Ones → Tens → Hundreds

LSD Radix Sort requires stable ordering at each digit position so that the results of earlier passes are preserved.

2. MSD Radix Sort

MSD stands for Most Significant Digit.

This method begins with the highest significant digit position and then processes lower positions inside the appropriate groups.

MSD implementations are often described using recursive partitioning of strings or digit keys.

Example: 472 Order of Processing: 4 → 7 → 2 Hundreds → Tens → Ones
Feature LSD Radix Sort MSD Radix Sort
Starting Position Least significant digit Most significant digit
Direction Right to left Left to right
Typical Method Stable digit passes Recursive grouping
Stability Stable if every pass is stable Depends on implementation
Common Use Fixed-width or bounded integer keys Strings and digit-prefix grouping

Exam Tip: LSD starts from the smallest place value. MSD starts from the largest significant place value. Their implementations are not interchangeable.

04 / Working Principle

How Does LSD Radix Sort Work?

The standard LSD Radix Sort process has four main steps.

STEP 01 Find Maximum

Determine how many digit positions are needed.

STEP 02 Choose Digit

Begin at the ones position.

STEP 03 Stable Sort

Arrange numbers by the current digit.

STEP 04 Repeat

Move to the next higher digit position.

How Digit Buckets Work

In decimal Radix Sort, each digit belongs to one of ten possible categories: 0 through 9.

We can imagine ten buckets. Numbers are grouped using the current digit while keeping the relative order within each group.

This bucket idea helps us understand the algorithm visually. The C implementation later uses stable Counting Sort to produce the same ordering.

05 / Solved Numerical

Radix Sort Example with Complete Dry Run

Consider the array:

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

We will sort these values using decimal LSD Radix Sort in ascending order.

Step 1: Find the Maximum Value

The largest number is 802, which has three digits.

Therefore, we need three digit passes: ones, tens and hundreds.

Pass 1: Sort by Ones Digit

First, find the last digit of every number.

Number Ones Digit
1700
455
755
900
8022
244
22
666

Ones-Digit Buckets

0 170, 90
1 —
2 802, 2
3 —
4 24
5 45, 75
6 66
7 —
8 —
9 —

Now collect the groups in digit order. Values sharing the same digit stay in their original relative order.

After Pass 1 (Ones): 170, 90, 802, 2, 24, 45, 75, 66

Pass 2: Sort by Tens Digit

Take the result of Pass 1 and sort by the tens digit.

Previous Order: 170 90 802 2 24 45 75 66 Tens Digits: 7 9 0 0 2 4 7 6

Sort these tens digits stably, keeping the previously established ones-digit order for equal tens digits.

After Pass 2 (Tens): 802, 2, 24, 45, 66, 170, 75, 90

Pass 3: Sort by Hundreds Digit

Now sort the result by the hundreds digit.

Previous Order: 802 2 24 45 66 170 75 90 Hundreds Digits: 8 0 0 0 0 1 0 0

Group the six numbers having hundreds digit zero, then the number with hundreds digit 1, and finally the number with hundreds digit 8.

After Pass 3 (Hundreds): 2, 24, 45, 66, 75, 90, 170, 802

Radix Sort Pass-by-Pass Table

Stage Digit Position Array After Pass
Original — 170, 45, 75, 90, 802, 24, 2, 66
Pass 1 Ones 170, 90, 802, 2, 24, 45, 75, 66
Pass 2 Tens 802, 2, 24, 45, 66, 170, 75, 90
Pass 3 Hundreds 2, 24, 45, 66, 75, 90, 170, 802
Final Sorted Array

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

The maximum number has three digits, so the standard decimal LSD method completes three passes.

Important Exam Point: After the ones-digit pass, the array is not necessarily fully sorted. Do not stop until all required higher digit positions are processed.

06 / Stable Digit Sorting

Radix Sort Using Counting Sort

Counting Sort is commonly used inside LSD Radix Sort.

In this approach, we do not count the frequency of complete numbers.

Instead, we count how many numbers contain each possible digit at the current place value.

Steps of Stable Counting Sort

  1. Find the current digit of every number.
  2. Count the frequency of digits from 0 to 9.
  3. Convert the counts into cumulative counts.
  4. Traverse the input from right to left.
  5. Place every element at its correct output position.
  6. Copy the completed output back into the original array.

Why Must Counting Sort Be Stable?

Stability means that two values with equal sorting keys keep their previous relative order during a pass.

For example, if 45 appears before 75, both have ones digit 5.

A stable ones-digit pass keeps 45 before 75 while grouping numbers by their ones digits.

Later digit passes must preserve the ordering of previously processed lower digits whenever the current digits are equal.

Key Concept: LSD Radix Sort is correct because each digit pass is stable. Using an unstable sorting method can destroy earlier digit ordering.

07 / Pseudocode

Radix Sort Algorithm in Data Structure

The following pseudocode explains decimal LSD Radix Sort for non-negative integers.

LSD Radix Sort Algorithm

RadixSort(A, n)
Algorithm RadixSort(A, n)

1. Find maximum value MAX in A

2. place = 1

3. While MAX / place > 0

       StableCountingSort(A, n, place)

       place = place * 10

4. Stop

Stable Counting Sort Pseudocode

CountingSortByDigit(A, n, place)
1. Create count[0..9] = 0

2. Create output[0..n-1]

3. For i = 0 to n-1

       digit = (A[i] / place) % 10

       count[digit]++

4. For digit = 1 to 9

       count[digit] += count[digit - 1]

5. For i = n-1 down to 0

       digit = (A[i] / place) % 10

       output[--count[digit]] = A[i]

6. Copy output into A

7. Return

Why Does the Loop Go from Right to Left?

Cumulative counts identify the ending position for each digit category.

By placing input elements from right to left and reducing the corresponding count, elements with equal digits keep their original relative order.

Important Variables in Radix Sort

Variable Purpose
n Number of array elements
MAX Largest input value
place Current digit position
digit Extracted digit from 0 to 9
count Digit frequencies and cumulative positions
output Temporary array for stable sorting
08 / Algorithm Analysis

Radix Sort Time Complexity and Space Complexity

Radix Sort's performance depends on three important quantities: number of elements, digit positions and size of the digit alphabet.

n = Number of elements d = Number of digit positions b = Base or radix Time = O(d × (n + b))
O(d(n+b)) Time per complete sort
O(n+b) Auxiliary space
O(n+b) Stable Counting Sort per pass

Best-Case Time Complexity

The standard implementation processes every required digit position even if numbers are already sorted.

Therefore, for a fixed number of passes d, its running time follows O(d(n+b)).

Average-Case Time Complexity

Every digit pass counts, computes cumulative positions and copies the elements.

The total time remains O(d(n+b)) for the standard implementation.

Worst-Case Time Complexity

The same number of digit passes is required for an input with the same maximum digit length.

The standard LSD implementation therefore has worst-case time O(d(n+b)).

Radix Sort Time Complexity Derivation

A stable Counting Sort pass needs O(n+b) time to count frequencies, build cumulative positions and distribute elements.

If d digit positions must be processed, this work repeats d times.

One Digit Pass: O(n + b) Number of Passes: d Total: O(d × (n + b))

When Can Radix Sort Be O(n)?

If both digit count and radix are fixed constants, such as a fixed-width integer representation with a chosen constant base, the expression becomes O(n).

But if the number of digits increases with the input range, we must include d in the analysis.

Radix Sort Space Complexity

The counting-based algorithm uses an output array of size n and a counting array of size b.

Output Array = O(n) Counting Array = O(b) Total Auxiliary Space: O(n + b)

For base 10, b is constant, so the space complexity becomes O(n).

Case Complexity Condition
Best Time O(d(n+b)) Standard full-digit processing
Average Time O(d(n+b)) Stable digit passes
Worst Time O(d(n+b)) All d digit positions processed
Auxiliary Space O(n+b) Output and count arrays
Base-10 Space O(n) Fixed ten digit categories

Important: The common claim that Radix Sort always takes O(n) time is incomplete. Its performance depends on the digit length and the radix.

09 / Interactive Digit Workshop

Interactive Radix Sort Visualizer

The following Radix Sort visualizer shows how each number enters its current digit bucket.

You can follow the ones, tens, hundreds and higher digit positions one step at a time.

Digit Sorting Workshop

This simulator uses base-10 LSD Radix Sort with stable bucket collection.

LSD · Base 10 · Ascending

Enter 3 to 10 non-negative integers between 0 and 9999.

Array State
Current Digit: Not Started
Digit Buckets (0–9)
0 Current Pass
0 Bucket Placements
0 Completed Passes

Ready to start.

Practice Task: Try the default eight values. Then enter 91, 12, 41, 22, 11 and observe how stability preserves lower-digit ordering across passes.

10 / Programming Practical

Radix Sort Program in C with Output

The following C program implements LSD Radix Sort for non-negative integers.

It uses stable Counting Sort at every digit position and displays the complete array after each pass.

The program accepts up to 100 numbers, checks basic input validity and safely handles all-zero input.

Complete Radix Sort C Program

radix_sort.c — Complete C11 Program
#include <stdio.h>
#include <limits.h>

#define MAX 100
#define BASE 10

void printArray(const int a[], int n) {

    for (int i = 0; i < n; ++i) {

        printf(
            "%d%s",
            a[i],
            i == n - 1 ? "\n" : " "
        );
    }
}

void stableDigitSort(
    int a[],
    int n,
    long long place,
    int output[]
) {
    int counts[BASE] = {0};

    /* Count digit frequencies */

    for (int i = 0; i < n; ++i) {

        int digit =
            (int)((a[i] / place) % BASE);

        ++counts[digit];
    }

    /* Build cumulative counts */

    for (int digit = 1;
         digit < BASE;
         ++digit) {

        counts[digit] += counts[digit - 1];
    }

    /* Stable placement from right to left */

    for (int i = n - 1; i >= 0; --i) {

        int digit =
            (int)((a[i] / place) % BASE);

        output[--counts[digit]] = a[i];
    }

    /* Copy output back into the array */

    for (int i = 0; i < n; ++i) {

        a[i] = output[i];
    }
}

int main(void) {

    int a[MAX];
    int output[MAX];

    int n;
    int max = 0;
    int passes = 0;

    printf(
        "Enter number of elements (1-100): "
    );

    if (
        scanf("%d", &n) != 1 ||
        n < 1 ||
        n > MAX
    ) {

        puts("Invalid array size.");
        return 1;
    }

    printf(
        "Enter %d non-negative integers: ",
        n
    );

    for (int i = 0; i < n; ++i) {

        if (
            scanf("%d", &a[i]) != 1 ||
            a[i] < 0
        ) {

            puts(
                "Only non-negative integers "
                "are supported."
            );

            return 1;
        }

        if (a[i] > max) {
            max = a[i];
        }
    }

    /* Process digits from ones onward */

    for (
        long long place = 1;
        max / place > 0;
        place *= BASE
    ) {

        stableDigitSort(
            a,
            n,
            place,
            output
        );

        ++passes;

        printf(
            "After place %lld: ",
            place
        );

        printArray(a, n);
    }

    if (max == 0) {

        puts(
            "All values are zero; "
            "no digit passes required."
        );
    }

    printf("Sorted array: ");

    printArray(a, n);

    printf(
        "Digit passes: %d\n",
        passes
    );

    return 0;
}

Sample Input

Program Input
Enter number of elements (1-100): 8

Enter 8 non-negative integers:
170 45 75 90 802 24 2 66

Output of Radix Sort C Program

Verified Output
After place 1: 170 90 802 2 24 45 75 66

After place 10: 802 2 24 45 66 170 75 90

After place 100: 2 24 45 66 75 90 170 802

Sorted array: 2 24 45 66 75 90 170 802

Digit passes: 3

Explanation of the C Program

1. Read the Array

The main function accepts the number of elements and reads non-negative integer values.

2. Find the Maximum Value

The variable max stores the largest input value. Its digit count determines how many passes are needed.

3. Select the Current Digit

The variable place starts at 1, representing the ones position.

It becomes 10, 100, 1000 and so on while additional digit positions remain.

4. Count Digit Frequencies

The counts array stores how many values belong to every digit group.

5. Calculate Cumulative Counts

Cumulative counts are used to calculate positions inside the temporary output.

6. Preserve Stable Ordering

The input array is traversed from right to left during placement.

This preserves the relative ordering of values with equal current digits.

7. Copy the Sorted Pass

After placing every value into output, the temporary values are copied back into the input array.

8. Display the Result

The program prints the array after every digit pass, then shows the final result and number of passes.

Program Verification: This implementation was compiled successfully with GCC using the C11 standard. The sample output, repeated values, zero values, different digit lengths and large positive integer inputs were checked.

How to Run Radix Sort in VS Code

  1. Open VS Code with GCC installed.
  2. Create a file named radix_sort.c.
  3. Paste the complete C program.
  4. Open the terminal in VS Code.
  5. Compile the program using GCC.
  6. Run the executable and enter your values.
GCC Compilation Command
gcc -std=c11 -Wall -Wextra radix_sort.c -o radix_sort

In Windows PowerShell:

Run Executable
.\radix_sort.exe
11 / Input Limitations

Can Radix Sort Handle Negative Numbers?

Radix Sort can be adapted to handle negative integers, but the simple decimal LSD program shown above supports non-negative integers only.

One possible extension is to separate negative and non-negative numbers. Negative numbers can be arranged according to absolute magnitude and then placed before non-negative numbers in the correct order.

Such an implementation must also handle the minimum representable integer safely.

Another approach processes fixed-width signed integer bits using an appropriate ordering transformation.

Important: Do not enter negative values into the C program in this chapter. It deliberately rejects them rather than giving incorrect sorting results.

12 / Compare Sorting Techniques

Radix Sort vs Counting Sort vs Quick Sort

Radix Sort and Counting Sort are non-comparison-based sorting techniques.

Quick Sort is a comparison-based sorting algorithm that partitions values around pivots.

Feature Radix Sort Counting Sort Quick Sort
Method Sort digit positions Count key frequencies Pivot partitioning
Comparison-Based? No No Yes
Typical Time O(d(n+b)) O(n+k) O(n log n) average
Typical Extra Space O(n+b) O(n+k) O(log n) expected stack
Stable? LSD with stable passes Stable implementation available Normally not stable
Best Suited For Suitable digit keys Small key range General-purpose array sorting

Radix Sort vs Counting Sort

Counting Sort directly counts the occurrences of keys from a limited range.

Radix Sort processes individual digits and can use Counting Sort as a subroutine.

A major difference is that Counting Sort may require a counting array related to the complete key range.

Radix Sort instead works with the smaller digit alphabet during each pass.

Radix Sort vs Quick Sort

Quick Sort compares values against pivots and recursively partitions the array.

Radix Sort processes digit positions without direct complete-key comparisons.

Radix Sort can be efficient for suitable fixed-width keys, but it also requires additional memory in its standard form.

13 / Practical Use

Advantages, Disadvantages and Applications of Radix Sort

Advantages of Radix Sort

  • Avoids repeated comparisons of complete keys.
  • Can perform well for suitable fixed-width integer or character keys.
  • Supports stable sorting with stable digit passes.
  • Provides predictable per-digit work for a chosen radix.
  • Can be adapted to different digit bases.

Disadvantages of Radix Sort

  • Requires additional output storage in the standard approach.
  • Performance depends on key length and radix.
  • Signed integers need special handling.
  • Stable per-digit sorting is essential for LSD correctness.
  • It may be unsuitable for complex keys without a useful digit representation.

Applications of Radix Sort

Radix-based methods are useful when records contain integer keys, fixed-length identifiers or strings that can be represented using a suitable finite alphabet.

Practical implementations may use digits, bytes or groups of bits instead of individual decimal digits.

14 / Common Errors

Common Mistakes in Radix Sort

Mistake Correct Explanation
Starting LSD with the hundreds digit LSD begins at the least significant digit.
Using unstable sorting on each digit Use stable digit ordering to preserve previous passes.
Ignoring shorter numbers Missing higher digits are treated as zero.
Writing Radix Sort always takes O(n) Use O(d(n+b)) for the standard analysis.
Claiming O(1) auxiliary space Standard Counting Sort-based LSD Radix Sort uses O(n+b).
Processing only the first digit Continue until all required positions are processed.
Using the non-negative version for signed input Handle negative values separately or use an appropriate signed-key representation.

Why Does Stability Matter So Much?

Suppose numbers are correctly grouped by ones digit.

If a later tens-digit pass unnecessarily changes the order of values with equal tens digits, the earlier ones-digit ordering can be lost.

This is why stability is a fundamental property of the standard LSD algorithm.

15 / Semester Exam Preparation

Important Radix Sort Questions and Answers

These original exam-style questions are useful for BCA, MCA and university practical preparation.

2 MARKS

1. Define Radix Sort.

Radix Sort is a non-comparison-based sorting algorithm that arranges values by processing individual digits or characters.

2 MARKS

2. What Is LSD in Radix Sort?

LSD stands for Least Significant Digit. It begins sorting from the rightmost digit and continues towards higher place values.

2 MARKS

3. What Is MSD Radix Sort?

MSD Radix Sort processes the most significant digit first and then handles lower digit positions within the required groups.

2 MARKS

4. Why Is Stable Sorting Required?

Stable sorting preserves the previously established lower-digit order when current digit values are equal.

5 MARKS

5. Explain Radix Sort with an Example.

Radix Sort processes numbers according to digit positions.

In LSD Radix Sort, values are sorted stably by ones, then tens, then hundreds, and so on.

For example, 45, 12, 31, 24 becomes 31, 12, 24, 45 after the ones-digit pass.

After the tens-digit pass, the final sorted result is 12, 24, 31, 45.

5 MARKS

6. Differentiate LSD and MSD Radix Sort.

LSD starts with the least significant digit and processes higher positions using stable digit passes.

MSD begins with the most significant digit and commonly processes grouped subproblems recursively.

10 MARKS

7. Explain Radix Sort Algorithm and Complexity.

Radix Sort is a non-comparison-based sorting algorithm that arranges keys through digit processing.

In the standard decimal LSD method, we first find the maximum value to determine the required digit count.

Each digit position is then processed with a stable sorting algorithm such as Counting Sort.

The process starts from ones, then tens, hundreds and higher positions.

For n elements, d digit positions and radix b, stable Counting Sort takes O(n+b) per digit.

Therefore, the total time complexity is O(d(n+b)).

Its standard auxiliary space is O(n+b) because of temporary output and counting arrays.

The algorithm is stable when every digit pass is stable.

16 / Practice with Solutions

Radix Sort Practice Questions and MCQs

Question 1: Sort 21, 13, 42, 11 Using LSD Radix Sort.

Show Complete Solution

Original: 21, 13, 42, 11.

Ones-digit order: 21, 11, 42, 13.

Tens-digit order: 11, 13, 21, 42.

Final: 11, 13, 21, 42.

Question 2: What Does LSD Mean?

A. Largest Significant Digit
B. Least Significant Digit
C. Linear Sorting Digit
D. Last Sorted Data

Show Answer

B. Least Significant Digit. It refers to the rightmost digit in a positional number representation.

Question 3: Which Property Is Important for LSD Digit Sorting?

A. Recursion only
B. Stability
C. Binary search
D. Heap ordering

Show Answer

B. Stability. Stable passes preserve previously established lower-digit order.

Question 4: How Many Decimal Digit Passes Are Needed for 9865?

Show Calculation

The number 9865 contains four decimal digits.

Therefore, a full LSD sort with this maximum needs four passes: ones, tens, hundreds and thousands.

Question 5: Is Radix Sort Comparison-Based?

Show Answer

No. Standard Radix Sort processes digit categories rather than relying on pairwise comparisons of complete keys.

17 / Frequently Asked Questions

FAQs About Radix Sort in Data Structure

What is Radix Sort in simple words?

Radix Sort arranges numbers or keys by processing their digit or character positions.

What is the time complexity of Radix Sort?

Standard LSD Radix Sort using stable Counting Sort takes O(d(n+b)) time for d digit positions and radix b.

What is the space complexity of Radix Sort?

The standard Counting Sort-based implementation uses O(n+b) auxiliary space.

Is Radix Sort stable?

LSD Radix Sort is stable when every digit pass uses a stable sorting method.

What is the difference between LSD and MSD?

LSD begins with the least significant digit, while MSD begins with the most significant digit.

Why is Counting Sort used in Radix Sort?

Counting Sort efficiently arranges values by digit categories and can preserve stable ordering.

Can Radix Sort handle negative numbers?

Yes, using an appropriate modified implementation. The introductory C program in this chapter accepts only non-negative integers.

Is Radix Sort always O(n)?

No. Its general digit-pass time depends on d, n and b. When digit count and radix are fixed constants, the bound simplifies to O(n).

18 / One-Minute Revision

Radix Sort Quick Revision Notes

RADIX SORT Type: Non-Comparison-Based Decimal Radix: 10 LSD: Least Significant Digit First MSD: Most Significant Digit First Stable Digit Method: Counting Sort Time: O(d(n + b)) Auxiliary Space: O(n + b) For Fixed Base and Digit Count: O(n) Time Standard LSD Stability: Yes, with stable passes C Program: Non-Negative Integers

Memory Trick: Find Maximum → Start at Ones → Stable Sort → Move to Tens → Continue.

Conclusion

Radix Sort in Data Structure becomes easier once you understand digit positions and stable ordering.

Instead of repeatedly comparing complete numbers, the standard LSD method processes digits from the least significant to the most significant position.

Stable Counting Sort keeps the results of earlier passes in the correct order.

Its standard time complexity is O(d(n+b)), while auxiliary space complexity is O(n+b).

For semester examinations, practise a complete digit-by-digit dry run, understand the role of stability, write the C program and remember the difference between LSD and MSD.

Chapter 49 — Completed

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources