Java Program for Counting Sort Algorithm

A Java program for counting sort uses an array to count occurrences of each number, then reconstructs the sorted array; for example, countingSort(int[] arr) counts and sorts the input array in linear time.

Examples

Input[4, 2, 2, 8, 3, 3, 1]

Output[1, 2, 2, 3, 3, 4, 8]

Input[5, 4, 3, 2, 1]

Output[1, 2, 3, 4, 5]

Input[]

Output[]

How to Think About It

To sort numbers using counting sort, first find the largest number to know the range. Then create a count array to store how many times each number appears. Next, build the sorted array by placing numbers according to counts.

Algorithm

1

Find the maximum value in the input array.

2

Create a count array of size max+1 and initialize with zeros.

3

Count each element's frequency in the input array and store in count array.

4

Build the output sorted array by placing elements at their correct positions using the count array.

5

Copy the sorted elements back to the original array.

Code

java

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }
        int[] count = new int[max + 1];
        for (int num : arr) {
            count[num]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Output

1 2 2 3 3 4 8 

Dry Run

Let's trace the array [4, 2, 2, 8, 3, 3, 1] through the counting sort code.

1

Find max value

max = 8

2

Initialize count array

count = [0,0,0,0,0,0,0,0,0] (length 9)

3

Count frequencies

count after counting: [0,1,2,2,1,0,0,0,1]

4

Build sorted array

Place 1 once, 2 twice, 3 twice, 4 once, 8 once

5

Final sorted array

[1, 2, 2, 3, 3, 4, 8]

Number	Count after counting
0	0
1	1
2	2
3	2
4	1
5	0
6	0
7	0
8	1

Why This Works

Step 1: Counting frequencies

The code counts how many times each number appears using the count array, so we know the quantity of each number.

Step 2: Rebuilding sorted array

It then places each number back into the original array in order, repeating each number as many times as counted.

Step 3: No comparisons needed

Counting sort does not compare elements but uses counting, making it very fast for numbers in a small range.

Alternative Approaches

Counting sort with cumulative counts

java

public class CountingSortCumulative {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;
        int max = arr[0];
        for (int num : arr) if (num > max) max = num;
        int[] count = new int[max + 1];
        for (int num : arr) count[num]++;
        for (int i = 1; i < count.length; i++) count[i] += count[i - 1];
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

This version uses cumulative counts to place elements directly, preserving stability but uses extra space.

Using Arrays.sort()

java

import java.util.Arrays;
public class SimpleSort {
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        Arrays.sort(arr);
        for (int num : arr) System.out.print(num + " ");
    }
}

This uses built-in sort which is easy but slower (O(n log n)) and not counting sort.

Complexity: O(n + k) time, O(k) space

Time Complexity

Counting sort runs in O(n + k) where n is the number of elements and k is the range of input values, because it counts frequencies and then rebuilds the array.

Space Complexity

It uses O(k) extra space for the count array, which depends on the maximum input value.

Which Approach is Fastest?

Counting sort is faster than comparison-based sorts like quicksort when k is not much larger than n, but uses more memory.

Approach	Time	Space	Best For
Counting Sort (basic)	O(n + k)	O(k)	Integers with small range
Counting Sort (cumulative)	O(n + k)	O(n + k)	Stable sort for integers
Arrays.sort()	O(n log n)	O(1)	General sorting, any data type