Radix Sort

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];
    }
}