# Radix Sort in Data Structure

Mentor: Shailendra Chauhan
Duration : 00:02:00

## What is Radix Sort in Data Structures?

Radix Sort is a linear, non-comparative sorting algorithm that processes components digit by digit. It sorts the array digit by digit from least to most significant. It first combines the individual digits with the same place value. It then sorts the components in increasing/decreasing order.

• Determine the maximum number of digits (d) in the array's greatest element.
• Create buckets, each representing a digit between 0 and 9.
• Iterate through each digit position (least to most significant).
• To sort the items by their current digit position, use counting sort.
• Repeat the process until all digits have been considered, giving a fully sorted array.

## Complexity Analysis of Radix Sort Algorithm

### Time Complexity

#### Best Case Complexity

This occurs when no sorting is necessary, implying that the array is already sorted. Radix sort has a best-case time complexity of Î©(n + k).

#### Average Case Complexity

This arises when the array elements are jumbled and do not appropriately ascend or descend. Radix sort has an average case time complexity of Î¸(nk).

#### Worst Case Complexity

This occurs when array members must be sorted in reverse order. That is, assume you need to sort the array elements in ascending order but the elements are in descending order. The worst-case temporal complexity for Radix sort is O(nk).

### Space Complexity

The Radix Sort algorithm has a space complexity of O(max).

• Integer Sorting: Radix sort sorts fixed-size integers, such as 32-bit integers, linearly by digit position.
• String Sorting: Radix sort arranges strings of fixed or common length by character position, allowing for efficient sorting.
• IP Address Sorting: Radix sort sorts IP addresses by octet, which is useful for network applications.
• Phone Number Sorting: Radix Sort sorts phone numbers by digit position.
• Data Radix Transformation: Radix sort converts data into several radix representations, such as decimal to binary or hex.