What is the Radix Sort in DSA ?? with free explanation

Overview

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing individual digits. It processes digits from the least significant to the most significant (LSD) or vice versa (MSD). The sorting is done using a stable subroutine like Counting Sort or Bucket Sort for each digit.

Key Characteristics

Time Complexity: O(d(n + k)), where d is the number of digits, n is the number of elements, and k is the range of digits (0-9 for decimal).
Space Complexity: O(n + k), where k is the range of digits.
Stability: Stable (maintains the relative order of equal elements).
Algorithm Type: Non-comparison-based sorting.

How Radix Sort Works

Find the Maximum Number:
- Determine the number of digits in the largest number.
Sort by Each Digit:
- Starting from the least significant digit (LSD) to the most significant digit (MSD), sort the array using a stable sort (e.g., Counting Sort).

Steps and Example

Consider the following unsorted array:

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

Step 1: Find the Maximum Number
- The largest number is 802, which has 3 digits.
Step 2: Sort by Each Digit
- Sort by the Least Significant Digit (LSD):
  - Original array: [170, 45, 75, 90, 802, 24, 2, 66]
  - After sorting by LSD: [170, 90, 802, 2, 24, 45, 75, 66]
- Sort by the Second Least Significant Digit:
  - Array after LSD sort: [170, 90, 802, 2, 24, 45, 75, 66]
  - After sorting by second LSD: [802, 2, 24, 45, 66, 170, 75, 90]
- Sort by the Most Significant Digit (MSD):
  - Array after second LSD sort: [802, 2, 24, 45, 66, 170, 75, 90]
  - After sorting by MSD: [2, 24, 45, 66, 75, 90, 170, 802]

Visualization

Let’s generate a step-by-step visualization of Radix Sort using diagrams.

Initial Array

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

Step 1 : Sort by LSD

Original: [170, 45, 75, 90, 802, 24, 2, 66]
Sort by LSD: [170, 90, 802, 2, 24, 45, 75, 66]

Step 2 : Sort by Second LSD

Array after LSD sort: [170, 90, 802, 2, 24, 45, 75, 66]
Sort by second LSD: [802, 2, 24, 45, 66, 170, 75, 90]

Step 3 : Sort by MSD

Array after second LSD sort: [802, 2, 24, 45, 66, 170, 75, 90]
Sort by MSD: [2, 24, 45, 66, 75, 90, 170, 802]