# What is Radix Sort

**Radix sort**is a sorting algorithm that works by comparing the digits of numbers. It's like sorting a bunch of phone numbers by area code first, and then by the rest of the digits.

Here's an example: Let's say you have the numbers 12, 23, 45, 67, and 89. To sort them using radix sort, you start by looking at the least significant digit (the rightmost digit) of each number. You group the numbers based on that digit, so you end up with two groups: one group with numbers ending in 2, and another group with numbers ending in 3, 5, 7, and 9. You then take the numbers in each group and sort them based on the next least significant digit (the tens place), so you end up with four groups: one with numbers starting with 2, one with numbers starting with 3, one with numbers starting with 4 or 6, and one with numbers starting with 5 or 8. You repeat this process, sorting based on each digit position until the numbers are sorted in ascending order.

Radix sort is a bit more complex than some other sorting algorithms, but it can be very efficient for certain types of data, particularly when the range of possible values is known in advance.

## Who invented it?

The

**radix sort**algorithm was invented by the American computer scientist Herman Hollerith in the late 19th century. Hollerith was working on ways to tabulate and analyze data for the U.S. Census, and he developed a machine called the tabulating machine that used punch cards to store and sort data. The radix sort algorithm was a key part of this machine's sorting process, and it helped to revolutionize the field of data processing.

Since then, the radix sort algorithm has been refined and improved by many other computer scientists, and it remains an important sorting algorithm today, especially in applications that involve large amounts of data with known integer ranges.

## Pseudocode

```
radix_sort(list)
// Find the maximum number in the list to determine the number of digits.
max_num = maximum(list)
num_digits = count_digits(max_num)
// Iterate through each digit, starting with the least significant digit.
for i = 0 to num_digits - 1
// Create 10 empty buckets for each possible digit (0-9).
buckets = array of 10 empty lists
// Put each number in the list into the appropriate bucket based on its current digit.
for number in list
digit = get_digit(number, i)
buckets[digit].add(number)
// Concatenate the lists in order to get the new sorted list.
list = concatenate(buckets)
return list
```

In this pseudocode, maximum(list) is a function that returns the maximum number in the list, count_digits(num) is a function that returns the number of digits in a number num, get_digit(num, i) is a function that returns the i-th digit of a number num (counting from the rightmost digit), and concatenate(buckets) is a function that concatenates all the lists in the buckets array in order.

## Sample Code

```
// C++ code snippet
// Get the maximum number in the array
int getMax(vector
``` arr) {
int max_num = arr[0];
for (int i = 1; i < arr.size(); i++) {
if (arr[i] > max_num) {
max_num = arr[i];
}
}
return max_num;
}
// Count the number of digits in a number
int countDigits(int num) {
int count = 0;
while (num != 0) {
num /= 10;
count++;
}
return count;
}
// Get the i-th digit of a number (counting from the rightmost digit)
int getDigit(int num, int i) {
for (int j = 0; j < i; j++) {
num /= 10;
}
return num % 10;
}
// Perform radix sort on the array
void radixSort(vector& arr) {
int max_num = getMax(arr);
int num_digits = countDigits(max_num);
for (int i = 0; i < num_digits; i++) {
// Create 10 empty buckets for each possible digit (0-9).
vector> buckets(10);
// Put each number in the array into the appropriate bucket based on its current digit.
for (int j = 0; j < arr.size(); j++) {
int digit = getDigit(arr[j], i);
buckets[digit].push_back(arr[j]);
}
// Concatenate the lists in order to get the new sorted array.
arr.clear();
for (int j = 0; j < 10; j++) {
arr.insert(arr.end(), buckets[j].begin(), buckets[j].end());
}
}
}
int main() {
// Example usage
vector arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}

```
# Python code snippet
def radix_sort(arr):
max_num = max(arr)
num_digits = len(str(max_num))
for i in range(num_digits):
# Create 10 empty buckets for each possible digit (0-9).
buckets = [[] for _ in range(10)]
# Put each number in the array into the appropriate bucket based on its current digit.
for j in range(len(arr)):
digit = int(str(arr[j])[i]) if i < len(str(arr[j])) else 0
buckets[digit].append(arr[j])
# Concatenate the lists in order to get the new sorted array.
arr = [elem for sublist in buckets for elem in sublist]
return arr
# Example usage
arr = [170, 45, 75, 90, 802, 24, 2, 66]
arr_sorted = radix_sort(arr)
print(arr_sorted)
```

```
import java.util.Arrays;
public class RadixSort {
public static int[] radixSort(int[] arr) {
int max_num = Arrays.stream(arr).max().getAsInt();
int num_digits = (int) Math.log10(max_num) + 1;
for (int i = 0; i < num_digits; i++) {
// Create 10 empty buckets for each possible digit (0-9).
int[][] buckets = new int[10][arr.length];
int[] bucket_sizes = new int[10];
// Put each number in the array into the appropriate bucket based on its current digit.
for (int j = 0; j < arr.length; j++) {
int digit = getDigit(arr[j], i);
buckets[digit][bucket_sizes[digit]++] = arr[j];
}
// Concatenate the lists in order to get the new sorted array.
int index = 0;
for (int j = 0; j < 10; j++) {
for (int k = 0; k < bucket_sizes[j]; k++) {
arr[index++] = buckets[j][k];
}
}
}
return arr;
}
private static int getDigit(int num, int i) {
return (num / (int) Math.pow(10, i)) % 10;
}
public static void main(String[] args) {
// Example usage
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
int[] arr_sorted = radixSort(arr);
System.out.println(Arrays.toString(arr_sorted));
}
}
```

## Time and Space Complexity

The time complexity of radix sort is O(d * (n + k)), where d is the number of digits in the maximum number, n is the number of elements in the input array, and k is the range of the input (i.e., the number of possible values each digit can have, typically 10 for decimal numbers). This makes radix sort a linear time sorting algorithm, as the time complexity is proportional to the size of the input.

The space complexity of radix sort is O(n + k), as we need to allocate space for the input array, the buckets, and the output array. This is also proportional to the size of the input, but with a relatively small constant factor (i.e., the size of the buckets).

The space complexity of radix sort is O(n + k), as we need to allocate space for the input array, the buckets, and the output array. This is also proportional to the size of the input, but with a relatively small constant factor (i.e., the size of the buckets).

## Advantages

- Radix sort has a linear time complexity, which means it can be very fast for large datasets, especially when compared to other sorting algorithms that have a worst-case time complexity of O(n log n).
- Radix sort is a stable sorting algorithm, which means it preserves the relative order of equal elements in the input array.
- Radix sort can sort numbers in different bases, not just decimal numbers.

## Disadvantages

- Radix sort requires additional memory to store the buckets used in the sorting process, which can make it less memory-efficient than other sorting algorithms that sort in-place (i.e., without using additional memory).
- Radix sort may not be as efficient as other sorting algorithms for small datasets or datasets with a small range of values.
- Radix sort may be less intuitive to understand and implement than other sorting algorithms.