Below is an example of the Radix Sort algorithm in Java. See the Radix Sort page for more information and implementations.
class RadixSort { public static void main(String[] args) { int[] array1 = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8}; int[] array2 = {2, 1, 5, 2, 9, 1, 2, 3, 3, 4, 4, 5, 6, 7, 8}; RadixSort radixSort = new RadixSort(); radixSort.sort(array1); radixSort.sort(array2); System.out.println(java.util.Arrays.toString(array1)); System.out.println(java.util.Arrays.toString(array2)); } void sort(int[] array) { // get the largest number to know how many place values we need to sort int maxValue = array[0]; for (int i = 1; i < array.length; i++) if (array[i] > maxValue) maxValue = array[i]; // sort the array at each placeValue for (int placeValue = 1; maxValue / placeValue > 0; placeValue *= 10) countingSort(array, placeValue); } private void countingSort(int[] array, int placeValue) { // step 1: create an empty array that will store the sorted version of the array int[] output = new int[array.length]; // step 2: create an empty array that will track the placeValue frequency int[] placeValueFrequency = new int[10]; // step 3: find the amount of times the array has a value in the placeValue we're searching for for (int i = 0; i < array.length; i++) { int value = (array[i] / placeValue) % 10; placeValueFrequency[value]++; } // step 4: reposition the indexes so that the indexes with smaller placeValues are moved to the beginning of the array for (int i = 1; i < 10; i++) placeValueFrequency[i] += placeValueFrequency[i - 1]; // step 5: starting from the end of the array, add each index index from the original array to the output array // the frequency - 1 of the value in the current placeValue will represent the index to place the original index for (int i = array.length - 1; i >= 0; i--) { int value = (array[i] / placeValue) % 10; // the value of the current placeValue output[placeValueFrequency[value] - 1] = array[i]; placeValueFrequency[value]--; } // step 6: copy the more sorted version of the array back into the original array for (int i = 0; i < array.length; i++) array[i] = output[i]; } }