Sorting - Counting Sort

Implement Counting Sort. It works by counting the occurrences of each distinct element, then using arithmetic to determine the positions of each element in the output sequence.

Input: [4,2,2,8,3,3,1] → Output: [1,2,2,3,3,4,8]

Input: [1,0,3,1,3,1] → Output: [0,1,1,1,3,3]

Count frequency of each element (given a known range 0..k). Compute prefix sums to get positions. Place each element in its correct output position.

Find min and max of the array to determine range k.
Create count[] of size k+1 and count each element.
Compute prefix sums: count[i] += count[i-1].
Iterate original array backwards and place each element at count[arr[i]]-1.

import java.util.Arrays; class CountingSort { public int[] sort(int[] arr) { if (arr.length == 0) return arr; int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); int range = max - min + 1; int[] count = new int[range]; int[] output = new int[arr.length]; for (int v : arr) count[v - min]++; for (int i = 1; i < range; i++) count[i] += count[i - 1]; for (int i = arr.length - 1; i >= 0; i--) { output[--count[arr[i] - min]] = arr[i]; } return output; } }

Time Complexity: O(N + K) where K is range
Space Complexity: O(N + K)