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.

Example 1

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

Example 2

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

Solution Approach

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.

Java

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)