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)

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.