Sorting Algorithms- 6 - Algorithms - Computer Science Engineering (CSE)

Radix Sort

Radix Sort is a non-comparison-based integer-sorting algorithm that sorts numbers by processing individual digits. It relies on a stable subroutine (commonly Counting Sort) to sort elements by a single digit position, and repeats this process for each digit from least significant to most significant (or vice versa).

Motivation and when to use

Comparison-based sorting algorithms such as Merge Sort, Heap Sort and Quick Sort have a lower bound of Ω(n log n) for sorting n arbitrary elements. When the keys to be sorted are integers in a bounded range, non-comparison sorts can be faster. Counting Sort sorts in O(n + k) time when elements lie in the range 1..k, but if k is very large (for example k = n²) Counting Sort becomes impractical.

Radix Sort addresses such cases by sorting numbers digit by digit, using a stable digit-sorting routine. It is effective when keys can be represented as sequences of digits (or fixed-size words) and when the number of digits is small relative to n.

High-level idea

Radix Sort processes digits of numbers one at a time, using a stable sort at each pass. Two common variants are:

• LSD (Least Significant Digit) Radix Sort - start sorting from the least significant digit and move towards the most significant digit. This is the typical variant when using Counting Sort as the stable subroutine.
• MSD (Most Significant Digit) Radix Sort - start from the most significant digit and recursively sort buckets. MSD is useful for variable-length keys and can be implemented recursively.

The Radix Sort algorithm (LSD variant)

1. Find the maximum element to determine the number of digits d.
2. For i = 0 to d - 1 (i denotes the current digit position, typically powers of base b):
3. Sort the array using a stable sort (commonly Counting Sort) according to digit i.
4. After the final pass, the array is fully sorted.

Why must the digit sort be stable?

Stability ensures that when two elements have the same digit in the current position, their relative order from the previous pass is preserved. For LSD Radix Sort, this property is essential to build the final correct order after successive passes.

Worked example (LSD, decimal)

Original list:

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

Sort by the 1s place (least significant digit). Maintain stability (preserve previous relative order):

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

Sort by the 10s place (next digit):

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

Sort by the 100s place (most significant digit here):

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

Note: In the intermediate step, 802 stays before 2 because 802 occurred earlier in the previous pass; this demonstrates stability.

Time and space complexity

Let n be the number of elements, b be the base (radix) used to represent digits (for decimal b = 10) and d be the number of digits per key.

• Each pass costs O(n + b) using Counting Sort as the stable subroutine.
• There are d passes, so total time is O(d × (n + b)).
• The value of d depends on the maximum key value k and base b: d = O(log_b k).
• Substituting gives overall time O((n + b) × log_b k).
• If k ≤ n^c for constant c and base b = n, then d = O(1)×log_n n^c = O(c), and the complexity can be made effectively linear, O(n), ignoring constants and space overhead.
• Space complexity is typically O(n + b) due to the output array and the count/bucket structures.

Practical considerations

• Choice of base b: Larger b reduces number of passes d but increases cost of each counting/bucket pass (cost depends on b). Choosing b around the machine word size or a power of two (so digits align with bit groups) is common for efficiency.
• Constants and cache behaviour: Radix Sort tends to have higher constant factors and may use more extra memory than comparison sorts. Quick Sort often uses hardware caches more effectively, so in practice Radix Sort is preferable when keys are integers/strings and many keys share similar lengths or d is small.
• Stability: Radix Sort requires a stable digit-sorting subroutine. Counting Sort is a natural choice because it is stable and runs in O(n + b).
• When Radix Sort is preferable: when keys are fixed-length integers/strings, the number of digits is small, and when an O(n) behaviour is desired for large datasets with suitable key encoding.

Variants

• LSD Radix Sort: Iterative, stable sort per digit from least to most significant. Simple and common for fixed-width integers.
• MSD Radix Sort: Recursive, partitions by the most significant digit and recursively sorts buckets. Useful for variable-length keys and can reduce work for datasets with shared prefixes.
• Bucket-based Radix (bin/bucket sort): Use arrays of buckets (often linked lists) to collect elements for each digit and then concatenate buckets. Stability must be maintained when collecting and writing back elements.

Algorithm pseudocode (LSD Radix using Counting Sort)

radix_sort(arr): m = maximum value in arr exp = 1 while m / exp > 0: counting_sort_by_digit(arr, exp) exp = exp * b # b is the base (e.g., 10 for decimal)

Stable digit counting sort (summary)

Counting sort by digit (digit determined by (arr[i] / exp) % b) proceeds as follows:

1. Compute frequency counts for digits 0..b-1.
2. Transform counts to positions by prefix-summing counts.
3. Build output array by iterating input from right to left and placing each element at the appropriate output position (this preserves stability).
4. Copy output back to input array.

Implementations

The following implementations illustrate the LSD Radix Sort using Counting Sort as the stable digit sorter. Code comments and contributor attributions from the original implementations are preserved.

• C++

  // C++ implementation of Radix Sort #include <iostream> using namespace std; // A utility function to get maximum value in arr[] int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. void countSort(int arr[], int n, int exp) { int output[n]; // output array int i, count[10] = { 0 }; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort void radixsort(int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that instead // of passing digit number, exp is passed. exp is 10^i // where i is current digit number for (int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp); } // A utility function to print an array void print(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } // Driver Code int main() { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call radixsort(arr, n); print(arr, n); return 0; }

• Java

  // Radix sort Java implementation import java.io.*; import java.util.*; class Radix { // A utility function to get maximum value in arr[] static int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. static void countSort(int arr[], int n, int exp) { int output[] = new int[n]; // output array int i; int count[] = new int[10]; Arrays.fill(count, 0); // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort static void radixsort(int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp); } // A utility function to print an array static void print(int arr[], int n) { for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } /*Driver Code*/ public static void main(String[] args) { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.length; // Function Call radixsort(arr, n); print(arr, n); } } /* This code is contributed by Devesh Agrawal */

• Python

  # Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len(arr) # The output array elements that will have sorted arr output = [0] * (n) # initialize count array as 0 count = [0] * (10) # Store count of occurrences in count[] for i in range(0, n): index = (arr[i] / exp1) count[int(index % 10)] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range(1, 10): count[i] += count[i - 1] # Build the output array i = n - 1 while i >= 0: index = (arr[i] / exp1) output[count[int(index % 10)] - 1] = arr[i] count[int(index % 10)] -= 1 i -= 1 # Copying the output array to arr[], # so that arr now contains sorted numbers i = 0 for i in range(0, len(arr)): arr[i] = output[i] # Method to do Radix Sort def radixSort(arr): # Find the maximum number to know number of digits max1 = max(arr) # Do counting sort for every digit. Note that instead # of passing digit number, exp is passed. exp is 10^i # where i is current digit number exp = 1 while max1 / exp > 0: countingSort(arr, exp) exp *= 10 # Driver code arr = [170, 45, 75, 90, 802, 24, 2, 66] # Function Call radixSort(arr) for i in range(len(arr)): print(arr[i]) # This code is contributed by Mohit Kumra # Edited by Patrick Gallagher

• C#

  // C# implementation of Radix Sort using System; class GFG { public static int getMax(int[] arr, int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i] > mx) mx = arr[i]; return mx; } // A function to do counting sort of arr[] according to // the digit represented by exp. public static void countSort(int[] arr, int n, int exp) { int[] output = new int[n]; // output array int i; int[] count = new int[10]; // initializing all elements of count to 0 for (i = 0; i < 10; i++) count[i] = 0; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // Copy the output array to arr[], so that arr[] now // contains sorted numbers according to current digit for (i = 0; i < n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort public static void radixsort(int[] arr, int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp); } // A utility function to print an array public static void print(int[] arr, int n) { for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } // Driver Code public static void Main() { int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.Length; // Function Call radixsort(arr, n); print(arr, n); } // This code is contributed by DrRoot_ }

• PHP

  <?php // PHP implementation of Radix Sort // A function to do counting sort of arr[] // according to the digit represented by exp. function countSort(&$arr, $n, $exp) { $output = array_fill(0, $n, 0); // output array $count = array_fill(0, 10, 0); // Store count of occurrences in count[] for ($i = 0; $i < $n; $i++) $count[ ($arr[$i] / $exp) % 10 ]++; // Change count[i] so that count[i] // now contains actual position of // this digit in output[] for ($i = 1; $i < 10; $i++) $count[$i] += $count[$i - 1]; // Build the output array for ($i = $n - 1; $i >= 0; $i--) { $output[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $count[ ($arr[$i] / $exp) % 10 ]--; } // Copy the output array to arr[], so // that arr[] now contains sorted numbers // according to current digit for ($i = 0; $i < $n; $i++) $arr[$i] = $output[$i]; } // The main function to that sorts arr[] // of size n using Radix Sort function radixsort(&$arr, $n) { // Find the maximum number to know // number of digits $m = max($arr); // Do counting sort for every digit. Note // that instead of passing digit number, // exp is passed. exp is 10^i where i is // current digit number for ($exp = 1; $m / $exp > 0; $exp *= 10) countSort($arr, $n, $exp); } // A utility function to print an array function PrintArray(&$arr,$n) { for ($i = 0; $i < $n; $i++) echo $arr[$i] . " "; } // Driver Code $arr = array(170, 45, 75, 90, 802, 24, 2, 66); $n = count($arr); // Function Call radixsort($arr, $n); PrintArray($arr, $n); // This code is contributed by rathbhupendra ?>

Bucket / bin-based Radix implementation (example)

The following C++ example shows a bucket/bin-based implementation using singly linked lists as buckets. It performs the same digit-by-digit processing but uses explicit buckets and linked lists to preserve stability.

// implementation of radix sort using bin/bucket sort #include <bits/stdc++.h> using namespace std; // structure for a single linked list to help further in the // sorting struct node { int data; node* next; }; // function for creating a new node in the linked list struct node* create(int x) { node* temp = new node(); temp->data = x; temp->next = NULL; return temp; } // utility function to append node in the linked list // here head is passed by reference, to know more about this // search pass by reference void insert(node*& head, int n) { if (head == NULL) { head = create(n); return; } node* t = head; while (t->next != NULL) t = t->next; t->next = create(n); } // utility function to pop an element from front in the list // for the sake of stability in sorting int del(node*& head) { if (head == NULL) return 0; node* temp = head; // storing the value of head before updating int val = head->data; // updation of head to next node head = head->next; delete temp; return val; } // utility function to get the number of digits in the // max_element int digits(int n) { int i = 1; if (n < 10) return 1; while (n > (int)pow(10, i)) i++; return i; } void radix_sort(vector<int>& arr) { // size of the array to be sorted int sz = arr.size(); // getting the maximum element in the array int max_val = *max_element(arr.begin(), arr.end()); // getting digits in the maximum element int d = digits(max_val); // creating buckets to store the pointers node bins; // array of pointers to linked list of size 10 as // integers are decimal numbers so they can hold numbers // from 0-9 only, that's why size of 10 bins = new node*[10]; // intializing the hash array with null to all for (int i = 0; i < 10; i++) bins[i] = NULL; // first loop working for a constan time only and inner // loop is iterating through the array to store elements // of array in the linked list by their digits value for (int i = 0; i < d; i++) { for (int j = 0; j < sz; j++) // bins updation insert(bins[(arr[j] / (int)pow(10, i)) % 10], arr[j]); int x = 0, y = 0; // write back to the array after each pass while (x < 10) { while (bins[x] != NULL) arr[y++] = del(bins[x]); x++; } } } // a utility function to print the sorted array void print(vector<int> arr) { for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; cout << endl; } int main() { vector<int> arr = { 573, 25, 415, 12, 161, 6 }; // function call radix_sort(arr); print(arr); return 0; }

Output for this example: 6 12 25 161 415 573

Time complexity remains the same as the Counting Sort based method; the difference is in implementation detail and memory layout.

Comparison with comparison-based sorts

• Asymptotically Radix Sort can be faster than comparison sorts for appropriate choices of base and when d is small relative to n.
• Radix Sort often uses extra memory and has larger constant factors; practical performance depends on data distribution, key sizes, choice of base, and implementation details (cache behaviour, memory allocation).
• For general-purpose sorting of arbitrary comparable items, comparison sorts such as Quick Sort or Merge Sort are still widely used. For large arrays of fixed-size integer keys or strings, Radix Sort is a strong candidate.

Summary

Radix Sort is a stable, digit-by-digit non-comparison sort that can achieve linear-time behaviour for suitably bounded integer keys by processing digits using a stable subroutine such as Counting Sort. Its time complexity is O(d (n + b)), and careful choice of base and implementation determines its practical efficiency.

Output example

Output

2 24 45 66 75 90 170 802

Snapshots