The counting sort flow starts by calculating the minimum and the maximum element in the array. Based on the computed minimum and maximum, the algorithm defines a new array that will be used to count the unsorted elements by using the element as the index. Furthermore, this new array is modified in such a way that each element at each index stores the sum of previous counts. Finally, the sorted array is obtained from this new array.
The time complexity cases are as follows: best case O(n + k), average case O(n + k), worst case O(n + k)
The space complexity case is as follows: worst case O(k)
n is the number of elements to be sorted.
Let's consider a quick example. The initial array contains the following elements, arr: 4, 2, 6, 2, 6, 8, 5:
The minimum element is 2 and the maximum element is 8. The new array, counts, will have a size equal to the maximum minus the minimum + 1 = 8 - 2 + 1 = 7.
Counting each element will result in the following array (counts[arr[i] - min]++):
counts[2] = 1 (4); counts[0] = 2 (2); counts[4] = 2 (6);
counts[6] = 1 (8); counts[3] = 1 (5);
Now, we must loop this array and use it to reconstruct the sorted array as in the following implementation:
public static void countingSort(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
int[] counts = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
counts[arr[i] - min]++;
}
int sortedIndex = 0;
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
arr[sortedIndex++] = i + min;
counts[i]--;
}
}
}
This is a very fast algorithm.