Loading…
Loading…
Sorts one digit at a time from least significant to most, using a stable bucket pass per digit — O(d · n), no comparisons.
The largest value is 100, so 3 digit passes will do it. Every pass sorts by ONE digit and must be stable.
1void radixSort(int[] arr) {2 int max = Arrays.stream(arr).max().orElse(0);3 for (int exp = 1; exp <= max; exp *= 10) { // one pass per digit4 List<List<Integer>> buckets = new ArrayList<>();5 for (int b = 0; b < 10; b++) buckets.add(new ArrayList<>());6 for (int x : arr)7 buckets.get((x / exp) % 10).add(x); // stability is mandatory — it preserves the previous digit's order8 int i = 0;9 for (List<Integer> b : buckets) // concatenate 0…910 for (int x : b) arr[i++] = x;11 }12}