Radix Sort in Java Time Complexity and Memory Allocation Explained
If you are sorting large arrays of integers, IDs, timestamps, or other numeric keys, radix sort is worth understanding. The big questions are simple:
How fast is radix sort, really?
Why is it often described as `O(n)`?
How much memory does a Java implementation allocate?
What choices make it faster or more expensive?
Radix sort works by sorting one digit group at a time
Radix sort does not ask whether `42 < 317`. Instead, it processes pieces of each value, usually from the least significant part to the most significant part.
For decimal numbers, that means:
Sort by the ones digit.
Sort by the tens digit.
Sort by the hundreds digit.
Keep going until all digit positions have been processed.
For binary data in Java, it is more common to process bytes rather than decimal digits. An `int` has 32 bits, so it has four 8-bit chunks. If you use base 256, each pass sorts one byte.
That gives you four passes for every `int` value:
```text
Pass 1: lowest 8 bits
Pass 2: next 8 bits
Pass 3: next 8 bits
Pass 4: highest 8 bits
```
Each pass usually uses counting sort internally. Counting sort is stable, which means equal digit groups keep their previous relative order. That stability is what lets later passes build on earlier passes.
Here is the core idea:
```text
Original values:
170, 45, 75, 90, 802, 24, 2, 66
After sorting by ones digit:
170, 90, 802, 2, 24, 45, 75, 66
After sorting by tens digit:
802, 2, 24, 45, 66, 170, 75, 90
After sorting by hundreds digit:
2, 24, 45, 66, 75, 90, 170, 802
```
The example uses decimal digits for readability. In real Java integer sorting, byte-based radix sort is usually faster because bit operations are cheap and the number of passes is fixed.
Time complexity depends on passes, array size, and radix
The usual time complexity for radix sort is:
```text
O(d × (n + b))
```
Where:
`n` is the number of elements in the array
`d` is the number of digit groups or passes
`b` is the radix, also called the base or bucket count
If you sort Java `int` values using 8 bits per pass:
`d = 4`
`b = 256`
`n` is the array length
So the complexity becomes:
```text
O(4 × (n + 256))
```
Since `4` and `256` are constants, this is commonly shortened to:
```text
O(n)
```
That statement is valid for fixed-width integers. A Java `int` always has 32 bits. A Java `long` always has 64 bits. The number of passes does not grow as the array grows.
Still, `O(n)` does not mean "always faster than comparison sort." Constant costs matter.
A comparison sort such as quicksort, mergesort, or Java’s built-in object sort usually has a comparison-based lower bound around:
```text
O(n log n)
```
Radix sort avoids comparisons, which can make it faster for very large primitive arrays. But it also reads and writes the array multiple times. For small arrays, the overhead of several passes and extra memory may not pay off.
For fixed-width primitive integers, radix sort is linear in the number of elements, but it still performs several full passes over the data.
That is the practical way to read radix sort complexity.
A concrete Java `int` example
Suppose you use base 256 for an `int[]`.
Each pass does three main things:
Count how many values fall into each byte bucket.
Convert counts into positions.
Move values into an output array in stable order.
For `n` values and 256 buckets, one pass costs roughly:
```text
n reads for counting
256 count operations
n reads and writes for distribution
```
Do that four times for a 32-bit `int`.
So the work grows like this:
```text
about 4 full counting scans
about 4 full distribution scans
small fixed bucket work
```
This is why radix sort often performs well on large arrays. The work is predictable, branch-light, and mostly sequential memory access.
Memory allocation in Java comes from the output array and counts
Radix sort is not usually an in-place algorithm. A typical Java implementation allocates:
One output array of length `n`
One count array of length `b`
Sometimes another temporary array or repeated arrays per pass
For an `int[]` sorted with base 256, the core extra memory is:
```text
int[] output = new int[n];
int[] count = new int[256];
```
An `int` uses 4 bytes. Ignoring object headers and alignment for a moment:
```text
output memory = 4 × n bytes
count memory = 4 × 256 bytes = 1,024 bytes
```
The count array is tiny. The output array is the main cost.
For example:
Array length | Input array size | Extra output array | Count array |
100,000 ints | About 0.4 MB | About 0.4 MB | About 1 KB |
1,000,000 ints | About 4 MB | About 4 MB | About 1 KB |
10,000,000 ints | About 40 MB | About 40 MB | About 1 KB |
These are approximate raw data sizes. Actual Java arrays also include object header and alignment overhead, but the big picture stays the same. The extra `int[n]` dominates.
The most common memory mistake is allocating a new output array during every pass. For a four-pass `int` radix sort, this creates avoidable garbage.
Avoid this pattern:
```java
for (int shift = 0; shift < 32; shift += 8) {
int[] output = new int[array.length]; // avoid repeated allocation
int[] count = new int[256];
// pass logic
}
```
This version may still work, but it puts pressure on the garbage collector. For large arrays, repeated allocation can cost more than expected.
A better design allocates once and reuses memory:
```java
int[] output = new int[array.length];
int[] count = new int[256];
for (int shift = 0; shift < 32; shift += 8) {
Arrays.fill(count, 0);
// pass logic
}
```
That reduces garbage and makes runtime more stable.
Swapping array references saves copying
After each pass, the sorted pass result is in the output buffer. Rather than copying every element back into the input array after each pass, many implementations swap references:
```java
int[] from = array;
int[] to = output;
//
after one pass
int[] temp = from;
from = to;
to = temp;
```
At the end, if the final sorted data is not in the original array, copy it once:
```java
if (from != array) {
System.arraycopy(from, 0, array, 0, array.length);
}
```
This avoids extra full-array copies between passes.
A practical Java implementation for non-negative integers
The following implementation sorts non-negative `int` values using base 256. It keeps allocation simple and predictable.
```java
import java.util.Arrays;
public final class RadixSort {
private static final int BITS_PER_PASS = 8;
private static final int RADIX = 1 << BITS_PER_PASS; // 256
private static final int MASK = RADIX - 1; // 255
public static void sortNonNegative(int[] array) {
if (array == null || array.length < 2) {
return;
}
int[] output = new int[array.length];
int[] count = new int[RADIX];
int[] from = array;
int[] to = output;
for (int shift = 0; shift < Integer.SIZE; shift += BITS_PER_PASS) {
Arrays.fill(count, 0);
for (int value : from) {
int bucket = (value >>> shift) & MASK;
count[bucket]++;
}
int sum = 0;
for (int i = 0; i < RADIX; i++) {
int c = count[i];
count[i] = sum;
sum += c;
}
for (int value : from) {
int bucket = (value >>> shift) & MASK;
to[count[bucket]++] = value;
}
int[] temp = from;
from = to;
to = temp;
}
if (from != array) {
System.arraycopy(from, 0, array, 0, array.length);
}
}
}
```
This code makes one large allocation, `output`, and one small allocation, `count`.
The time complexity is:
```text
O(4 × (n + 256))
```
The extra memory complexity is:
```text
O(n + 256)
```
Since 256 is constant, people usually write the memory complexity as:
```text
O(n)
```
What about negative numbers?
The method above is for non-negative integers. Negative numbers need extra handling because Java uses two’s complement representation. If you simply sort all 32 bits as unsigned chunks, negative values will appear after positive values.
There are several ways to handle this.
One common method is to flip the sign bit during bucket calculation, or adjust the final pass so signed order is preserved. The idea is to treat `Integer.MIN_VALUE` as the smallest value and `Integer.MAX_VALUE` as the largest.
For the last pass only, you can offset the top byte:
```java
int bucket = ((value >>> shift) & MASK);
if (shift == 24) {
bucket ^= 128;
}
```
This remaps the sign bit so negative values come before non-negative values in the final signed order.
If you need production-ready signed sorting, test heavily with values like:
```java
Integer.MIN_VALUE
-1
0
1
Integer.MAX_VALUE
```
Edge cases matter with radix sort because the byte transformation defines the final order.
Radix choice changes speed and memory
Base 256 is popular because it processes 8 bits per pass. But it is not the only choice.
You could use 4 bits per pass:
Radix is 16
Passes for `int` are 8
Count array is very small
You could use 16 bits per pass:
Radix is 65,536
Passes for `int` are 2
Count array is much larger
Here is the tradeoff:
Bits per pass | Radix | Passes for `int` | Count array size |
4 | 16 | 8 | 16 ints |
8 | 256 | 4 | 256 ints |
16 | 65,536 | 2 | 65,536 ints |
A 16-bit pass reduces the number of full array scans, but the count array becomes much larger. It may still be reasonable in some cases, since 65,536 integers take about 256 KB of raw storage. But larger count arrays can interact poorly with CPU caches.
Base 256 is often a good middle ground:
Only four passes for `int`
Small count array
Simple bit operations
Good cache behavior
This is why many examples and practical implementations start there.
When radix sort makes sense in Java
Radix sort is a strong fit when the keys are fixed-width primitive values and the data set is large enough to justify multiple passes.
Good use cases include:
Sorting large `int[]` or `long[]` arrays
Sorting numeric IDs
Sorting encoded timestamps
Sorting records by integer keys when you can move indexes or references carefully
It may be a poor fit when:
The array is small
You are sorting complex objects with expensive movement
You cannot afford an extra array of size `n`
You need a simple general-purpose sort
The key transformation is hard to get right
Java’s standard library sorting methods are already well tested and highly tuned for general use. For primitive arrays, `Arrays.sort(int[])` is usually the right default. Radix sort becomes interesting when you know your data shape and need predictable linear behavior.
The key point is memory. If you sort 50 million integers, the input array alone is already large. A radix sort needs another array of the same length unless you use a more complex in-place variant. That extra allocation can decide whether the algorithm is practical.
The main takeaway
Radix Sort in Java time complexity and memory allocation come down to three numbers: the array length, the number of passes, and the radix size.
For a byte-based Java `int` radix sort:
```text
Time complexity: O(4 × (n + 256)), usually written as O(n)
Extra memory: O(n + 256), usually written as O(n)
```
The output array is the main memory cost. The count array is small when you use base 256. To keep Java performance steady, allocate buffers once, reuse the count array, swap references between passes, and copy back only if needed.
Radix sort is not magic, but it is powerful when the data matches the algorithm. For large primitive integer arrays, it can turn sorting into a small fixed number of simple, predictable scans.
Comments