Counting Sort Algorithm

What is Counting Sort?

Counting Sort is a non-comparison-based sorting algorithm that sorts integers by counting the occurrences of each unique value in the array. It works best when the input elements are non-negative integers within a small range.

Unlike algorithms like Quick Sort or Merge Sort, Counting Sort does not use comparisons to sort elements. Instead, it relies on the idea that if you know how many elements are smaller than each value, you can place them directly into the correct position.

How Counting Sort Works

1. Find the maximum value in the input array to determine the range.
2. Create a count array of size max + 1, where each index represents a value from the input.
3. Count the occurrences of each value and store them in the count array.
4. Modify the count array to contain the cumulative sum of counts.
5. Use the count array to place elements into a sorted output array.
6. (Optional) Copy the sorted array back into the original array.

Characteristics of Counting Sort

• Time Complexity:
  • Best, Average, Worst: O(n + k), where n is the number of elements and k is the range of input.
• Space Complexity: O(n + k)
• Stability: ✅ Yes
• In-place: ❌ No (needs auxiliary arrays)

When to Use Counting Sort

• You are sorting non-negative integers (or can shift them to be).
• The range of input values is not significantly greater than the number of elements.
• You need a stable and linear-time sort for specific use cases (e.g., Radix Sort subroutine).

Code Example

public class CountingSortExample {

    public static void countingSort(int[] arr) {
        int n = arr.length;

        // Find the maximum value in the array
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // Create count array of size (max + 1)
        int[] count = new int[max + 1];

        // Store the frequency of each value
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }

        // Reconstruct the sorted array
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Original array:");
        printArray(arr);

        countingSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output

Original array:
4 2 2 8 3 3 1 
Sorted array:
1 2 2 3 3 4 8 

Counting Sort – Visual Explanation (Step-by-Step)

Let’s sort the array:

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

Step 1: Count Frequencies

Create a count array to track occurrences of each value from 0 to 8 (the max):

count[0] = 0  
count[1] = 1  
count[2] = 2  
count[3] = 2  
count[4] = 1  
count[5–7] = 0  
count[8] = 1

Count array:

[0, 1, 2, 2, 1, 0, 0, 0, 1]

Step 2: Reconstruct Sorted Array

Walk through the count array and for each value i, write it to the original array count[i] times:

1 → 1 time
2 → 2 times
3 → 2 times
4 → 1 time
8 → 1 time

Reconstructed sorted array:

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

Final Sorted Array

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

Summary

• Counting Sort is incredibly fast for sorting integers with a small range.
• It does not use comparisons, making it unique among sorting algorithms.
• Time complexity is linear, but space complexity depends on the range.
• Best suited for large datasets with small integers and no negative values.