Radix Sort

Problem

Radix Sort is a non-comparative sorting algorithm that sorts integers by processing individual digits. It sorts numbers from the least significant digit to the most significant digit, using a stable sort for each digit position.

Examples:

Example 1:
Input: arr = [170, 45, 75, 90, 802, 24, 2, 66]
Output: [2, 24, 45, 66, 75, 90, 170, 802]
Explanation: The algorithm sorts the array by processing each digit position from right to left.

Example 2:
Input: arr = [121, 432, 564, 23, 1, 45, 788]
Output: [1, 23, 45, 121, 432, 564, 788]
Explanation: The algorithm efficiently sorts the array by considering each digit position separately.

Solution

Intuition

  • Radix Sort works by sorting numbers digit by digit, from the least significant digit (rightmost) to the most significant digit (leftmost).
  • It uses a stable sorting algorithm (usually Counting Sort) as a subroutine to sort the numbers according to each digit.
  • The algorithm processes all digits of the largest number in the array.
  • Since it sorts based on digits rather than comparing elements, Radix Sort can achieve linear time complexity for a fixed number of digits.

Approach

  • Find the maximum number in the array to determine the number of digits.
  • For each digit position (starting from the least significant digit):
  • - Sort the array based on the current digit position using a stable sort (like Counting Sort).
  • - Move to the next digit position.
  • Repeat until all digit positions are processed.

Complexity Analysis

  • 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 each digit (usually 10 for decimal numbers).
  • Space Complexity: O(n + k) for the temporary arrays used in the counting sort subroutine.
Implementation
CPP
Run your code to see output here