Radix sort
Radix sort is a non-comparative sorting algorithm that processes integers or fixed-length keys by distributing elements into buckets based on individual digits (or characters in a given base), typically starting from the least significant digit and proceeding to the most significant digit using a stable sub-sorting routine like counting sort.[1] This digit-by-digit approach avoids direct comparisons between elements, making it suitable for sorting large datasets of numbers or strings where the key length is bounded.[2] The algorithm traces its origins to 1887, when Herman Hollerith developed an early form of radix sorting for mechanical tabulating machines to efficiently process U.S. Census data using punched cards, enabling rapid sorting by multiple fields in passes through the machine.[3] Hollerith's system, patented in 1889, alluded to a most-significant-digit-first variant and laid the groundwork for data processing innovations that contributed to the founding of what became IBM.[4] The first memory-efficient computerized version of radix sort was introduced in 1954 by Harold H. Seward in his MIT master's thesis, where he formalized it alongside counting sort for electronic digital computers applied to business operations.[5] In practice, radix sort operates in O(d(n + k)) time complexity, where n is the number of elements, d is the number of digits in the keys, and k is the radix (base, often 10 for decimal), assuming a stable inner sort; this can achieve near-linear performance for fixed-length keys without the Ω(n log n) lower bound of comparison sorts.[1] Variants include least-significant-digit (LSD) radix sort, which is simpler and common for integers, and most-significant-digit (MSD) radix sort, which can be adaptive for variable-length keys like strings.[6] It requires O(n + k) auxiliary space for buckets and is widely used in applications such as database indexing, IP routing tables, and parallel computing environments due to its predictability and efficiency on uniform data.[7]Fundamentals
Overview
Radix sort is a non-comparative sorting algorithm that processes integers or fixed-length keys by grouping elements based on individual digits, starting from either the least significant digit or the most significant digit position.[8] This approach enables linear-time sorting under the model where the number of digits and the radix are treated as constants relative to the input size.[9] The radix, synonymous with the base r of the number representation, defines the range of possible digit values and directly determines the number of buckets used in the distribution step, with exactly r buckets created for each pass.[8] For instance, decimal representation uses base 10 and thus 10 buckets, while binary uses base 2 and 2 buckets.[8] In the general radix sort framework, the algorithm iterates over each digit position in the keys: elements are distributed into the appropriate buckets according to the current digit's value, and then collected in sequential order from the buckets to reconstruct the list for the next iteration.[10] This distribution and collection process depends on a stable subroutine, such as counting sort, to ensure that the relative order of elements with identical digits is preserved across passes.[10] A high-level pseudocode outline is as follows:[8]Algorithm RadixSort(A, r, d) Input: Array A of n elements with d digits in base r Output: Sorted array A for i = 1 to d do Create r empty buckets for each element x in A do digit = extract i-th digit of x in base r Add x to bucket[digit] A = concatenate buckets[0] to buckets[r-1] in orderAlgorithm RadixSort(A, r, d) Input: Array A of n elements with d digits in base r Output: Sorted array A for i = 1 to d do Create r empty buckets for each element x in A do digit = extract i-th digit of x in base r Add x to bucket[digit] A = concatenate buckets[0] to buckets[r-1] in order
Building Blocks
Counting sort serves as the primary stable subroutine underlying radix sort, enabling efficient distribution of elements based on individual digits or keys. It operates by first counting the occurrences of each possible key value in the input array, then using these counts to determine the final positions of elements in the output array. Specifically, for an input array of n elements with keys ranging from 0 to d-1, counting sort employs an auxiliary array C of size d (or d+1 if including a sentinel) to tally frequencies. The algorithm proceeds in three main phases: initializing the count array to zeros, incrementing counts for each input element, computing cumulative sums to establish output positions, and finally placing elements into the output array in a stable manner by iterating backward through the input to preserve relative order.[11][12] The pseudocode for counting sort, adapted from standard descriptions, illustrates these steps clearly:This implementation ensures stability by placing elements from the end of the input array, which maintains the original relative order of equal keys.[11][13] The time complexity of counting sort is O(n + d), arising from the two passes over the input array of size n and the operations on the count array of size d. This linear-time performance makes it ideal for radix sort when d is not excessively large compared to n. Stability is crucial in radix sort because it ensures that equal keys from previous digit passes retain their relative order during subsequent passes, allowing the overall algorithm to correctly resolve full key comparisons through iterative digit extractions.[12][14] In radix sort implementations, the distribution step of counting sort can be viewed as partitioning elements into d buckets (one per possible key value), with the count array effectively sizing and positioning these buckets. Simpler variants may use explicit arrays or queues as buckets for direct element placement during digit-based distribution, maintaining stability by appending to the end of each bucket rather than overwriting. This bucketing approach avoids comparisons and leverages the fixed key range for efficiency.[11][15]COUNTING-SORT(A, B, d) // A[1..n] is the input array, B[1..n] is the output array, d is the range 1. for i = 0 to d-1 2. C[i] = 0 3. for j = 1 to n 4. C[A[j]] = C[A[j]] + 1 5. // compute cumulative counts 6. for i = 1 to d-1 7. C[i] = C[i] + C[i-1] 8. for j = n downto 1 9. B[C[A[j]]] = A[j] 10. C[A[j]] = C[A[j]] - 1 11. for j = 1 to n 12. A[j] = B[j] // copy back if in-place not desiredCOUNTING-SORT(A, B, d) // A[1..n] is the input array, B[1..n] is the output array, d is the range 1. for i = 0 to d-1 2. C[i] = 0 3. for j = 1 to n 4. C[A[j]] = C[A[j]] + 1 5. // compute cumulative counts 6. for i = 1 to d-1 7. C[i] = C[i] + C[i-1] 8. for j = n downto 1 9. B[C[A[j]]] = A[j] 10. C[A[j]] = C[A[j]] - 1 11. for j = 1 to n 12. A[j] = B[j] // copy back if in-place not desired
Digit Ordering Approaches
Least Significant Digit Method
The least significant digit (LSD) method of radix sort processes keys digit-by-digit, beginning with the rightmost digit (least significant) and progressing leftward to more significant digits. This iterative approach relies on a stable sorting subroutine, such as counting sort, applied to each digit position to maintain the relative order of keys that share the same digit value in the current position.[16] The algorithm starts by stably sorting all keys based on their units place (lowest digit). It then repeats the stable sort on the resulting array using the next higher digit position (e.g., tens place), continuing iteratively until the highest digit position is processed. For variable-length keys, such as integers or strings with differing numbers of digits, the method pads shorter keys with leading zeros to normalize them to a fixed length equal to the maximum number of digits among all keys. This padding ensures uniform processing across all positions.[16] The following pseudocode illustrates the core loop of LSD radix sort for base-r keys with at most d digits:Each iteration employs the stable subroutine (e.g., counting sort) on the specified digit.[16] LSD radix sort features a simpler, non-recursive implementation that guarantees stability through its stable sub-sorts. It excels for equal-length keys, like fixed-precision integers, where the uniform digit count aligns well with the fixed number of passes. A drawback is that it always executes the full set of d passes, even if sorting lower digits already resolves the order, which may introduce overhead when higher digits are unnecessary.[17]for i from 0 to d-1 do stably sort the array using key ($k / r^i$) mod $r$ as the sort keyfor i from 0 to d-1 do stably sort the array using key ($k / r^i$) mod $r$ as the sort key
Most Significant Digit Method
The Most Significant Digit (MSD) method in radix sort begins processing keys from their leftmost (highest place value) digit, partitioning the input array into radix-sized buckets based on that digit's value and then recursively sorting each non-empty bucket using the next digit position. This recursive partitioning continues until all digits have been processed or subarrays are of size at most one.[18] Unlike methods requiring fixed-length keys, MSD naturally accommodates variable-length keys, such as strings or numbers with differing digit counts, by treating positions beyond a key's length as a special value (e.g., a leading zero or null character), allowing shorter keys to be grouped appropriately without explicit padding.[18] The core of the algorithm is a recursive procedure that first computes histograms for the current digit across the subarray, stably redistributes elements into temporary storage using counting sort principles, overwrites the original subarray, and then invokes itself on the resulting bucket subarrays for the subsequent digit. This approach leverages key-indexed counting for partitioning, ensuring that equal digits maintain relative order.[18] Pseudocode for MSD radix sort, adapted for an array A of keys with low and high indices defining the subarray and d as the current digit position (starting from 0 for the most significant digit), is as follows:Here,MSDSort(A, lo, hi, d): if lo >= hi: return count[0..R-1] ← 0 // R is the radix for i ← lo to hi: digit ← getDigit(A[i], d) // Extract digit at position d count[digit] ← count[digit] + 1 for i ← 1 to R-1: count[i] ← count[i] + count[i-1] temp[0..hi-lo] ← empty array for i ← hi downto lo: digit ← getDigit(A[i], d) temp[count[digit] - 1] ← A[i] count[digit] ← count[digit] - 1 for i ← lo to hi: A[i] ← temp[i - lo] for i ← 0 to R-1: rel_start ← count[i] rel_end ← if i < R-1 then count[i+1] - 1 else hi - lo if rel_start ≤ rel_end: MSDSort(A, lo + rel_start, lo + rel_end, d + 1)MSDSort(A, lo, hi, d): if lo >= hi: return count[0..R-1] ← 0 // R is the radix for i ← lo to hi: digit ← getDigit(A[i], d) // Extract digit at position d count[digit] ← count[digit] + 1 for i ← 1 to R-1: count[i] ← count[i] + count[i-1] temp[0..hi-lo] ← empty array for i ← hi downto lo: digit ← getDigit(A[i], d) temp[count[digit] - 1] ← A[i] count[digit] ← count[digit] - 1 for i ← lo to hi: A[i] ← temp[i - lo] for i ← 0 to R-1: rel_start ← count[i] rel_end ← if i < R-1 then count[i+1] - 1 else hi - lo if rel_start ≤ rel_end: MSDSort(A, lo + rel_start, lo + rel_end, d + 1)
getDigit(key, d) returns the digit at the d-th position from the most significant digit, or a sentinel value if beyond the key's length.[19]
Key advantages of MSD include early termination of recursion for subarrays of size 1 or those with identical remaining digits, which enhances efficiency on partially sorted inputs or data with common prefixes, such as strings in natural language; it is particularly effective for unequal-length keys where the top-down structure avoids unnecessary processing of trailing digits.[18]
However, challenges arise from the recursion depth equaling the maximum key length, which may cause stack overflow for extremely long keys in non-tail-recursive implementations; stability, while achievable through the underlying stable partitioning, requires precise handling to preserve order among equal keys across recursive levels.[18]
Illustrative Examples
LSD Sorting Process
To illustrate the LSD radix sort process, consider the unsorted array of integers [170, 45, 75, 90, 802, 24, 2, 66] in base 10, where the maximum number of digits is three (hundreds, tens, units). The algorithm performs iterative passes starting from the units place, using a stable sorting subroutine (typically counting sort) to distribute elements into buckets based on the current digit and then collect them in order while preserving relative positions of equal keys. Pass 1: Units DigitElements are sorted by their units digit (value modulo 10). The distribution into 10 buckets (0 through 9) is as follows, with elements appended in their original relative order for stability:
| Digit | Bucket Contents |
|---|---|
| 0 | 170, 90 |
| 1 | |
| 2 | 802, 2 |
| 3 | |
| 4 | 24 |
| 5 | 45, 75 |
| 6 | 66 |
| 7 | |
| 8 | |
| 9 |
Now sorting the intermediate array by the tens digit (value modulo 100, divided by 10), the buckets are:
| Digit | Bucket Contents |
|---|---|
| 0 | 802, 2 |
| 1 | |
| 2 | 24 |
| 3 | |
| 4 | 45 |
| 5 | |
| 6 | 66 |
| 7 | 170, 75 |
| 8 | |
| 9 | 90 |
Finally, sorting by the hundreds digit (value modulo 1000, divided by 100), the buckets are:
| Digit | Bucket Contents |
|---|---|
| 0 | 2, 24, 45, 66, 75, 90 |
| 1 | 170 |
| 2–7 | |
| 8 | 802 |
| 9 |
MSD Sorting Process
The MSD sorting process in radix sort involves recursively partitioning the input data based on the most significant digit (or character), distributing elements into buckets corresponding to possible digit values, and then applying the same partitioning recursively to each non-trivial bucket (those with more than one element). This top-down recursion naturally handles variable-length keys, such as strings, by treating the end of a string as smaller than any actual character, enabling lexicographical ordering. The process terminates early for buckets containing zero or one element, optimizing performance by avoiding further subdivisions.[20] To illustrate, consider sorting the strings ["BAN", "BAND", "AB", "ABC"] in base-26 (where A=0, B=1, ..., Z=25), assuming standard lexicographical order where shorter strings precede longer ones with matching prefixes. The initial recursive call at depth 0 examines the first character:- Bucket 0 (A): "AB", "ABC"
- Bucket 1 (B): "BAN", "BAND"
- Sub-bucket 1 (B): "AB", "ABC"
- Sub-sub-bucket 0 (end): "AB"
- Sub-sub-bucket 2 (C): "ABC"
- Sub-bucket 0 (A): "BAN", "BAND"
- Sub-sub-bucket 13 (N): "BAN", "BAND"
- Sub-sub-sub-bucket 0 (end): "BAN"
- Sub-sub-sub-bucket 3 (D): "BAND"
Collecting elements in order from the leaves (left to right, top to bottom) yields the fully sorted list: ["AB", "ABC", "BAN", "BAND"]. This demonstrates how MSD radix sort achieves ordering through hierarchical partitioning without direct comparisons between elements.[21]Root (depth 0) ├── Bucket 0 (A) │ └── Depth 1: Bucket 1 (B) │ ├── Depth 2: Bucket 0 (end) → "AB" │ └── Depth 2: Bucket 2 (C) → "ABC" └── Bucket 1 (B) └── Depth 1: Bucket 0 (A) └── Depth 2: Bucket 13 (N) ├── Depth 3: Bucket 0 (end) → "BAN" └── Depth 3: Bucket 3 (D) → "BAND"Root (depth 0) ├── Bucket 0 (A) │ └── Depth 1: Bucket 1 (B) │ ├── Depth 2: Bucket 0 (end) → "AB" │ └── Depth 2: Bucket 2 (C) → "ABC" └── Bucket 1 (B) └── Depth 1: Bucket 0 (A) └── Depth 2: Bucket 13 (N) ├── Depth 3: Bucket 0 (end) → "BAN" └── Depth 3: Bucket 3 (D) → "BAND"
Performance Analysis
Time and Space Complexity
The time complexity of radix sort depends on both the least significant digit (LSD) and most significant digit (MSD) variants, with derivations rooted in the use of stable sorting subroutines like counting sort for each digit position. For the LSD variant, the algorithm performs a fixed number of passes equal to the maximum number of digits d in the input keys, processing digits from least to most significant. Each pass employs counting sort, which requires O(n + r) time, where n is the number of elements and r is the radix (number of possible digit values). Thus, the total time complexity is O(d(n + r)). The space complexity for LSD radix sort is O(n + r), arising from the need for an auxiliary output array of size n and a counting array (or buckets) of size r per pass. This auxiliary space is reused across passes, keeping the overall requirement linear in the input size plus the radix. For the MSD variant, which processes digits recursively from most to least significant, the worst-case time complexity remains O(d(n + r)), as it may require full recursion depth d across all elements without early termination. However, in the average case, particularly for skewed data distributions where many keys share common prefixes, subtrees terminate early when all elements in a bucket are identical, yielding an expected time complexity of O(n). The space complexity mirrors that of LSD at O(n + r) in the worst case, though recursion depth can temporarily increase stack usage to O(d) in unbalanced cases. The total time can be expressed as T = d \cdot (n + r), highlighting the linear cost per pass. Performance is influenced by the choice of radix r: increasing r reduces d (fewer passes) but enlarges the per-pass cost O(r), creating a trade-off optimized for the word size and hardware; in practice, values like r = 2^8 or $2^{10} balance passes with cache efficiency for better real-world throughput.Stability and Comparisons
Radix sort maintains stability by relying on a stable underlying sorting mechanism, such as counting sort, for each digit position; this ensures that elements with equal keys retain their relative order from the input sequence.[9][22] Stability is crucial in radix sort, as processing digits sequentially preserves the ordering established in previous passes for equal elements.[6] In comparison to comparison-based algorithms like quicksort, which have an average time complexity of O(n log n), radix sort achieves linear time O(n) performance for integer keys with a fixed number of digits, making it more efficient for large datasets where direct key comparisons are unnecessary.[6][23] Radix sort generalizes bucket sort by distributing elements into buckets based on multiple digit positions rather than a single hash or range, enabling it to handle keys with structured representations beyond simple uniform distributions.[24] Radix sort excels in use cases involving fixed-width integers, such as sorting large arrays of numbers or IP addresses treated as sequences of bytes, and strings in lexicographic order, where the digit structure is known and uniform.[6][25] It is less suitable for arbitrary floating-point numbers without first mapping them to a digit-based representation, as the algorithm assumes keys can be decomposed into discrete digits or symbols.[26] Additionally, standard radix sort is not in-place, requiring auxiliary space proportional to the input size and radix value, though modifications can address this.[9]Historical Development
Origins and Early Work
The origins of radix sort trace back to 1887, when Herman Hollerith developed a mechanical tabulating system for the U.S. Census Bureau using punched cards to represent data in columns corresponding to digits or categories.[27] Hollerith's system employed a sorting process that distributed cards into pockets based on the position of holes in specific columns, effectively performing a radix sort by processing one column (or "digit") at a time, starting from the most significant digit, with subsequent passes on lower digits to refine the sorting.[4] This method, inspired by earlier Jacquard loom technology but adapted for data processing, allowed efficient sorting of large volumes of demographic information without direct comparisons between records.[27] In the early 20th century, Hollerith's innovations evolved into commercial punched-card equipment produced by the Tabulating Machine Company (later IBM), where mechanical sorters continued to implement radix-like sorting by hole positions as the least significant "digit" in base-12 or base-10 encodings.[4] These systems predated electronic digital computers, relying on physical distribution of cards into bins for each pass, and were widely used for business and governmental data processing into the 1940s.[28] By the 1940s and 1950s, as punch-card systems integrated with early electronic computers like the IBM 701, radix sorting principles were adapted for hybrid electromechanical workflows, bridging mechanical card handling with initial software routines for data preparation.[27] The first memory-efficient algorithmic description for computerized radix sort appeared in 1954, detailed by Harold H. Seward in his MIT report on applying digital computers to business operations, which formalized the method using stable counting sorts on digits to achieve linear time complexity for fixed-length keys.[29] This adaptation marked the transition of radix sort from hardware-based card sorting to software implementations on electronic machines.[30]Key Advancements
In the 1960s, radix sort received formal theoretical analysis within computer science, building on its earlier practical use to establish its place among efficient sorting algorithms. Donald Knuth provided a rigorous treatment of the algorithm in his influential text, examining both least significant digit (LSD) and most significant digit (MSD) approaches. Knuth detailed the mechanics of digit-by-digit distribution and collection, highlighting radix sort's non-comparative nature and its suitability for fixed-radix representations. Knuth's analysis in The Art of Computer Programming, Volume 3: Sorting and Searching (1973 edition) spans pages 506–542, where he derives performance bounds and compares radix sort to other methods like quicksort, emphasizing its linear-time potential under appropriate models. This formalization solidified radix sort's theoretical foundations, influencing subsequent algorithm design and implementation in programming languages. By the 1980s, advancements focused on radix sort's capability for linear-time sorting of integers, particularly within the random access machine (RAM) model that assumes constant-time word operations. Researchers demonstrated that, for integers bounded by the word size (typically O(\log n) bits), radix sort achieves O(n) time complexity by processing a constant number of digits per word. This recognition linked radix sort to the word RAM model, where it outperforms comparison-based sorts for integer data with bounded range. A pivotal 1984 paper by Kirkpatrick and Reisch established upper bounds for integer sorting on RAMs, introducing radix sort variants that extend linear-time performance to larger ranges through multi-pass refinements.[31] These developments underscored radix sort's efficiency in hardware-aligned models, paving the way for its adoption in systems programming. Radix sort adaptations in the late 20th century extended the algorithm beyond integers to strings and multi-key sorting, critical for database systems handling composite records. In multi-key scenarios, keys are treated as tuples of attributes, with radix sort applied sequentially across fields using LSD for uniformity or MSD for early partitioning.[32] This enabled efficient indexing and query processing in relational databases, where variable-length fields like names or addresses require character-level bucketing.[32] A landmark contribution was the 1997 paper by Jon Bentley and Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings," which introduced MSD radix sort variants optimized for strings.[32] Their hybrid approach integrates radix partitioning with quicksort pivoting, reducing passes for uneven-length keys and achieving practical speeds competitive with tuned libraries for text-heavy applications.[32] This work has been widely adopted in string sorting implementations, including those for database engines.[32] From the 2000s to 2025, the core radix sort algorithm has remained largely unchanged since the 1990s, with advancements centering on hardware optimizations for GPUs and big data environments. Parallel GPU implementations leverage thread-level parallelism for bucket distribution, enabling terabyte-scale sorting in distributed systems.[33] For example, early GPU radix sorts from 2009 achieved up to 10x speedups over CPU versions for million-element arrays.[33] Recent multi-GPU variants, such as the 2023 RMG Sort algorithm, use radix partitioning to balance load across devices, sorting billions of keys in seconds while minimizing inter-GPU communication.[34] These optimizations support big data frameworks like those in analytics pipelines, maintaining radix sort's stability and efficiency for massive, integer-dominant datasets.[34]Advanced Variants
In-Place and Stable Implementations
In-place implementations of radix sort modify the standard algorithm to operate directly on the input array, minimizing auxiliary space requirements through techniques like swapping and partitioning, which resemble those in quicksort but adapted for digit-based distribution. These variants are particularly useful for memory-constrained environments, as they avoid allocating full temporary arrays for bucketing. For most significant digit (MSD) radix sort, in-place operation is achieved by recursively partitioning the array based on the current digit, placing elements into their relative positions via swaps without extra storage proportional to the input size. The American flag sort exemplifies this approach, using a multi-pass partitioning scheme that scans the array multiple times—once per bucket—to compute positions and swap elements accordingly, effectively distributing items across hundreds of buckets in linear time per digit. This method, developed by M. Douglas McIlroy, blends efficiency with in-place constraints and has been influential in practical sorting libraries.[35] Achieving stability in in-place radix sort presents significant challenges, especially for least significant digit (LSD) variants, where each of the multiple passes must preserve the relative order of elements with identical digits to ensure correct overall sorting. LSD in-place stability is harder to attain than in MSD due to the sequential nature of passes, as unstable swaps in early passes can disrupt later ones; common solutions involve treating the array as an implicit linked list for insertion-like operations or employing careful swapping sequences to mimic stable bucketing with limited temporary variables. The MSL (Map Shuffle Loop) algorithm addresses this for LSD by adaptively processing digits through a loop that maps positions and shuffles elements via swaps, maintaining stability while using only constant auxiliary space beyond a small buffer for the radix size. The following pseudocode illustrates a simplified in-place stable partition for a single LSD pass (assuming a small radix r for clarity, with rotation used to shift blocks while preserving order; full LSD would repeat this for each digit position):This partition uses rotations (implementable in O(n) time with O(1) extra space via reversals) to ensure elements within the same bucket retain their original relative order after displacement. In-place variants, whether MSD or LSD, often incur a modest time penalty from the swapping and rotation overhead—potentially increasing the constant factors in the O(d n) complexity, where d is the number of digits—but reduce space to O(r) auxiliary (for counting arrays) or even O(1) with optimized counting. These trade-offs sacrifice the simplicity of out-of-place bucketing for substantial memory savings, proving valuable for sorting large datasets in resource-limited settings.[19]function stable_partition_inplace(A, low, high, digit_pos, r): // Count occurrences for each bucket 0 to r-1 counts = array of size r, initialized to 0 for i from low to high: d = extract_digit(A[i], digit_pos) counts[d] += 1 // Compute starting positions for each bucket (cumulative) starts = array of size r starts[0] = low for k from 1 to r-1: starts[k] = starts[k-1] + counts[k-1] // Use temporary array of size r for current positions (O(r) space) positions = copy of starts // Partition by swapping, using rotation for stable block moves when needed for i from low to high: d = extract_digit(A[i], digit_pos) if i != positions[d]: // Swap A[i] to its bucket start, then rotate the intervening block if necessary to maintain stability swap(A[i], A[positions[d]]) // Rotate the segment from positions[d]+1 to i to shift displaced elements right, preserving order if positions[d] < i: rotate_right(A, positions[d] + 1, i - positions[d]) positions[d] += 1function stable_partition_inplace(A, low, high, digit_pos, r): // Count occurrences for each bucket 0 to r-1 counts = array of size r, initialized to 0 for i from low to high: d = extract_digit(A[i], digit_pos) counts[d] += 1 // Compute starting positions for each bucket (cumulative) starts = array of size r starts[0] = low for k from 1 to r-1: starts[k] = starts[k-1] + counts[k-1] // Use temporary array of size r for current positions (O(r) space) positions = copy of starts // Partition by swapping, using rotation for stable block moves when needed for i from low to high: d = extract_digit(A[i], digit_pos) if i != positions[d]: // Swap A[i] to its bucket start, then rotate the intervening block if necessary to maintain stability swap(A[i], A[positions[d]]) // Rotate the segment from positions[d]+1 to i to shift displaced elements right, preserving order if positions[d] < i: rotate_right(A, positions[d] + 1, i - positions[d]) positions[d] += 1