Radix Sort
Visualize how integer arrays are sorted digit by digit using counting sort as a subroutine.
Radix Sort
Concept Overview
Radix Sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. It works by processing individual digits from the least significant digit (LSD) to the most significant digit (MSD) or vice versa, typically utilizing Counting Sort as a stable subroutine for sorting each digit.
Mathematical Definition
The time complexity of Radix Sort depends on the number of elements n, the base or radix b, and the maximum number of digits d required to represent the maximum element. For a chosen base b, the number of digits d is given by:
The inner loop uses Counting Sort which takes O(n + b) time and space. Since this is repeated d times, the total time complexity is O(d(n + b)). When d is constant, Radix Sort runs in linear time.
Comparison Summary
| Algorithm | Time (Worst Case) | Space (Worst Case) | Stable |
|---|---|---|---|
| Radix Sort (LSD) | O(d(n + b)) | O(n + b) | Yes |
| Counting Sort | O(n + k) | O(n + k) | Yes |
| Quick Sort | O(n2) | O(log n) | No |
| Merge Sort | O(n log n) | O(n) | Yes |
Key Concepts
- Least Significant Digit (LSD) Radix Sort: Processes digits starting from the least significant digit (rightmost) to the most significant digit (leftmost). It typically uses a stable sorting algorithm like Counting Sort to sort the digits. LSD is generally preferred for sorting integers.
- Most Significant Digit (MSD) Radix Sort: Processes digits from the most significant digit (leftmost) to the least significant digit (rightmost). It can be implemented recursively and is often used for sorting strings of variable length (lexicographical order).
- Stability: Stability is crucial for LSD Radix Sort. If the subroutine sorting algorithm (like Counting Sort) is not stable, sorting by the current digit could destroy the order established by sorting the previous, less significant digits.
- Base Choice (Radix): The performance of Radix Sort is highly dependent on the choice of the base b. A larger base means fewer digits d to process, but a larger base requires more space and time for the counting array in the Counting Sort subroutine.
Historical Context
Radix Sort's history predates modern computers. Its origins can be traced back to the punched card tabulating machines developed by Herman Hollerith in the late 19th century, which were used for the 1890 U.S. Census. These machines sorted cards column by column, essentially performing a physical version of Radix Sort.
When digital computers were invented, Radix Sort was one of the first sorting algorithms to be adapted for them. It was formalized by Harold H. Seward in 1954 at MIT. For many years, comparison-based sorting algorithms like Quick Sort and Merge Sort dominated due to their general-purpose nature and better caching performance on modern architectures, but Radix Sort has seen a resurgence in specific domains, especially in high-performance computing and GPU programming, where parallelized versions can vastly outperform comparison sorts for certain data types.
Real-world Applications
- Large-scale integer key sorting: Radix Sort is well suited for sorting records keyed by fixed-width integers such as account numbers, student IDs, or product codes, where the range of values is large but the key length is bounded.
- String and lexicographical ordering: Variants of Radix Sort (especially MSD) are used to sort strings such as log entries, URLs, or dictionary words by processing characters position by position.
- Database and indexing systems: Some storage engines and indexing structures leverage radix-based techniques to efficiently organize keys, especially when keys are fixed-length or can be encoded as integers.
- High-performance and parallel computing: On GPUs and multicore systems, parallel implementations of Radix Sort are used to reorder large datasets (e.g., particles in simulations or elements in graphics pipelines) because they can avoid expensive comparisons and exploit regular memory access patterns.
Related Concepts
- Counting Sort — the stable subroutine typically used within Radix Sort to sort individual digits.
- Bucket Sort — a distribution sort that operates similarly by distributing elements into "buckets" before sorting them.
- Sorting Algorithms — comparison-based sorting algorithms like Quick Sort, Merge Sort, and Heap Sort.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Radix Sort module.
Try Radix Sort on Riano →