This is a very fast algorithm, but can only be used with arrays with integer values.
This algorithm can be explained as follows:
- find minimum (min) and maximum (max) value in the integer array
- create a new array with length = max – min + 1 to store statistics
- iterate through the initial array and count the array values. Put the value statistics into the previously created array at indexes equal to the values
For example, the initial array:
[1, 2, 3, 2, 1, 5, 0], min = 0, max = 5
Statistics array:
[1, 2, 1, 1, 0, 1]
- iterate through a statistic array and restore the initial array:
[0, 1, 1, 2, 3, 5]
- time complexity: O(n+m), where n – the length of the initial array, m – the length of the statistical array
- space complexity: O(m)
import java.util.Arrays;
public class ImplementCountingSort {
private static void sort(int[] input) {
var min = Integer.MAX_VALUE;
var max = Integer.MIN_VALUE;
for (int j : input) {
if (j < min) {
min = j;
}
if (j > max) {
max = j;
}
}
var arrayLength = max - min + 1;
var counts = new int[arrayLength];
for (var i = 0; i < input.length; i++) {
counts[input[i] - min]++;
}
var i = 0;
for (var j = 0; j < counts.length; j++) {
while (counts[j] > 0) {
input[i] = min + j;
i++;
counts[j]--;
}
}
}
public static void main(String[] args) {
int[] array = {-6, -6, -6, 3, 2, 1};
System.out.println(Arrays.toString(array));
sort(array);
System.out.println(Arrays.toString(array));
}
}