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

• Benjamin Kuykendall: Why do you think the time complexity is O(n^2)? To me, it looks like each run of _LSBSort takes time O(n), and it is repeated w times.
• Bagira: Due to nested for loop in _LSBSort and if every deque is not null it will take O(n^2) time.
• Benjamin Kuykendall: Remember that each item in the list is in exactly one of the deques -- thus iterating through all 10 deques is only iterating through n objects in total.
• Bagira: but one qeque can have more than one element and iterating each deque is proportional to its size.
• Benjamin Kuykendall: Precisely. Say deques[i] contains si items, so iterating over it takes time O(si). Then the outer for loop takes time O(s1) + O(s2) ... + O(s10) = O(s1 + s2 + ... + s10). But since each item occurs in exactly one deque, we know s1 + s2 + ... + s10 = n. Conclude the loop takes time O(n).

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();
 }
 }
}