Counting Sort and Radix Sort

Counting Sort

Scope: Best for integers with a relatively small, known range (0 to $K$).

public void countingSort(int[] arr) {
    if (arr.length == 0) return;
    int max = Arrays.stream(arr).max().getAsInt();
    int[] frequency = new int[max + 1];
    
    for (int x : arr) frequency[x]++;
    
    // Convert to prefix sum to maintain stable sorting property
    for (int i = 1; i <= max; i++) frequency[i] += frequency[i-1];
    
    int[] output = new int[arr.length];
    // Traverse backwards to preserve stability
    for (int i = arr.length - 1; i >= 0; i--) {
        output[--frequency[arr[i]]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, arr.length);
}

Complexity: $O(N + K)$ time, $O(N + K)$ space.

Bucket Sort

Distribute elements into fixed-range buckets, sort each bucket individually, and then concatenate results.

public void bucketSort(float[] arr) {
    int n = arr.length;
    if (n <= 0) return;
    
    List<Float>[] buckets = new ArrayList[n];
    for (int i = 0; i < n; i++) buckets[i] = new ArrayList<>();
    
    // Assuming x in [0, 1) range
    for (float x : arr) {
        int index = (int) (x * n);
        buckets[index].add(x);
    }
    
    int position = 0;
    for (List<Float> bucket : buckets) {
        Collections.sort(bucket);
        for (float val : bucket) arr[position++] = val;
    }
}

Radix Sort

Sort by digits from least significant (LSD) to most significant, using counting sort as the stable subroutine.

public void radixSort(int[] arr) {
    int maxVal = Arrays.stream(arr).max().getAsInt();
    
    // Sort for every digit: 1s, 10s, 100s...
    for (int exponent = 1; maxVal / exponent > 0; exponent *= 10) {
        countingSortByDigit(arr, exponent);
    }
}

private void countingSortByDigit(int[] arr, int exponent) {
    int[] frequency = new int[10];
    int[] tempOutput = new int[arr.length];
    
    for (int x : arr) frequency[(x / exponent) % 10]++;
    for (int i = 1; i < 10; i++) frequency[i] += frequency[i-1];
    
    for (int i = arr.length - 1; i >= 0; i--) {
        int digit = (arr[i] / exponent) % 10;
        tempOutput[--frequency[digit]] = arr[i];
    }
    System.arraycopy(tempOutput, 0, arr, 0, arr.length);
}

Complexity: $O(D \cdot (N + K))$ where $D$ is the number of digits and $K=10$ for decimal.

Challenge: Maximum Gap (LeetCode 164)

Find the maximum difference between successive elements in a sorted array, but in Linear Time.

Bucket Strategy: If we distribute $N$ elements into $N+1$ buckets, the maximum gap cannot occur within a single bucket (Pigeonhole Principle). Thus, the gap is the difference between the minimum of a bucket and the maximum of the previous non-empty bucket.

public int maximumGap(int[] nums) {
    if (nums.length < 2) return 0;
    int min = Arrays.stream(nums).min().getAsInt();
    int max = Arrays.stream(nums).max().getAsInt();
    if (min == max) return 0;
    
    int n = nums.length;
    // Calculate bucket parameters
    int bucketSize = Math.max(1, (max - min) / (n - 1));
    int bucketCount = (max - min) / bucketSize + 1;
    
    int[] minValues = new int[bucketCount];
    int[] maxValues = new int[bucketCount];
    Arrays.fill(minValues, Integer.MAX_VALUE);
    Arrays.fill(maxValues, Integer.MIN_VALUE);
    
    for (int x : nums) {
        int idx = (x - min) / bucketSize;
        minValues[idx] = Math.min(minValues[idx], x);
        maxValues[idx] = Math.max(maxValues[idx], x);
    }
    
    int maxGap = 0;
    int previousMax = min;
    for (int i = 0; i < bucketCount; i++) {
        if (minValues[i] == Integer.MAX_VALUE) continue; // Skip empty buckets
        maxGap = Math.max(maxGap, minValues[i] - previousMax);
        previousMax = maxValues[i];
    }
    return maxGap;
}

Challenge: Top K Frequent Elements (LeetCode 347)

An O(N) strategy using frequency as the bucket index.

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> counts = new HashMap<>();
    for (int n : nums) counts.merge(n, 1, Integer::sum);
    
    // Max frequency is limited by array length
    List<Integer>[] freqBuckets = new ArrayList[nums.length + 1];
    for (var entry : counts.entrySet()) {
        int f = entry.getValue();
        if (freqBuckets[f] == null) freqBuckets[f] = new ArrayList<>();
        freqBuckets[f].add(entry.getKey());
    }
    
    List<Integer> result = new ArrayList<>();
    for (int i = nums.length; i >= 0 && result.size() < k; i--) {
        if (freqBuckets[i] != null) result.addAll(freqBuckets[i]);
    }
    return result.subList(0, k).stream().mapToInt(i -> i).toArray();
}