Time complexity of radix sort

Question

I read time complexity of radix sort is O(wn) or O(n log n), if all n numbers are distinct. After implementation it look to me as if I have implemented radix sort which has time complexity of O(n ^2). Please take a look at my implementation and suggest, if there is some implementation problem or my observation about time complexity is wrong.

Please note: I have hard coded few values for simplicity to sort 3 digit numbers only.

private void LSBSort(int[] arr) {
    _LSBSort(arr, 1);
}

private void _LSBSort(int[] arr, int divisor) {
    Deque[] deques = new Deque[10];
    for(int i = 0 ; i < arr.length ; i++) {
        int mod = (arr[i] /divisor ) % 10;
        if (deques[mod] == null) {
            deques[mod] = new ArrayDeque<>();
        }
        deques[mod].add(arr[i]);
    }
    divisor *= 10;
    if (divisor > 1000) {
        return;
    }

    int cursor = 0;
    for (int i = 0 ; i < 10 ; i++) {
        if (deques[i] != null) {
            for (int j = 0 ; j <= deques[i].size() ; j++) {
                cursor = cursor + j;
                arr[cursor] = (int)deques[i].pollFirst();
            }
            cursor++;
        }
    }
    _LSBSort(arr, divisor);
}

Answer 1

First: the runtime is O(wn), as it should be for this algorithm.

Consider a single run of _LSBSort. Let n be the length of arr. Clearly the first loop is time O(n). Let si be the length of deques[i]. Then the second loop is time $$ O(s_1) + O(s_2) + \dots + O(s_{10}) = O(s_1 + s_2 + \dots + s_{10}).$$ Noting that each element is present in exactly one of the deques, we conclude $$s_1 + s_2 + \dots + s_{10} = n.$$ Thus the entire method runs in time O(n). As it is called w times, we conclude the entire algorithm is O(wn) time.

Second: some comments on the code.

1. These methods should be static.
2. Use an ArrayList for deque. Arrays of generics are just too ugly.
3. Call the list deques because it is plural.
4. Initialize all the deques up front. Clear and reuse between iterations.
5. Use extended for loops throughout.
6. Use loop instead of recursion.

private static void LSBSort(int[] arr) {
    List<ArrayDeque<Integer>> deques = new ArrayList<>(10);
    for (int i = 0; i < 10; i++) {
        deques.add(new ArrayDeque<Integer>());
    }

    for (int d = 1; d <= 1000; d *= 10) {
        for(int i : arr) {
            deques.get((i / d) % 10).add(i);
        }

        int cursor = 0;
        for (Deque<Integer> D : deques) {
            for (Integer j : D) {
                arr[cursor++] = j;
            }

            D.clear();
        }
    }
}