Knowledge Guide
Home › DSA › Advanced Patterns

Counting Sort Algorithm

Counting Sort is a non-comparative sorting algorithm that sorts integers by counting the occurrences of each unique element. It then uses this count to determine the position of each element in the sorted output array. This algorithm is particularly effective when the range of the input elements is not significantly larger than the number of elements.

Counting Sort is best suited for sorting integers or objects that can be mapped to integers, making it efficient with a time complexity of , where n is the number of elements and k is the range of the input.

Counting Sort stands out because it is stable and works well with large datasets where the range of input values is manageable. It does not rely on comparisons, making it faster than comparison-based sorting algorithms in specific scenarios.

How Does Counting Sort Work?

We will learn the counting sort by applying it to the array = [4, 2, 2, 8, 3, 3, 1].

  1. Find the Maximum Value in the Array
    • This step determines the range of the input values to create an appropriately sized count array.
    • Traverse the array to find the maximum value.
Image
Image
  1. Create and Initialize the Count Array
    • Create a count array of size max + 1 where max is the maximum value found in the input array.
    • Initialize the count array to zero to ensure accurate counting.
Image
Image
  1. Count the Frequency of Each Element
    • Traverse the input array and for each element, increment the corresponding index in the count array.
    • This step tallies the number of times each element appears in the input array.
Image
Image
  1. Modify the Count Array to Store Cumulative Counts
    • Traverse the count array and update each element to be the sum of itself and the previous element.
    • This modification transforms the count array to store the cumulative count, which indicates the position of each element in the sorted array.
Image
Image
  1. Build the Output Array
    • Create an output array of the same size as the input array.
    • Traverse the input array in reverse order to make sorting stable:
      • For each element, place it in the output array at the position indicated by the count array, which is countArray[array[i]] - 1.
      • Decrement the corresponding index in the count array by one to account for the placement.
      • This ensures that the next occurrence of the same element is placed in the correct position in the output array.
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
Image
  1. Copy the Output Array Back to the Input Array
    • Copy the sorted elements from the output array back to the input array to complete the sorting process.

Algorithm Walkthrough

Input: array1 = [4, 2, 2, 8, 3, 3, 1]

  1. Find the Maximum Value in the Array

    • Maximum value = 8

  2. Create and Initialize the Count Array

    • Count array of size 8 + 1 = 9: [0, 0, 0, 0, 0, 0, 0, 0, 0]

  3. Count the Occurrences of Each Element

    • Traverse the input array: {4, 2, 2, 8, 3, 3, 1}
    • Update the count array:
      • countArray[4]++ -> [0, 0, 0, 0, 1, 0, 0, 0, 0]
      • countArray[2]++ -> [0, 0, 1, 0, 1, 0, 0, 0, 0]
      • countArray[2]++ -> [0, 0, 2, 0, 1, 0, 0, 0, 0]
      • countArray[8]++ -> [0, 0, 2, 0, 1, 0, 0, 0, 1]
      • countArray[3]++ -> [0, 0, 2, 1, 1, 0, 0, 0, 1]
      • countArray[3]++ -> [0, 0, 2, 2, 1, 0, 0, 0, 1]
      • countArray[1]++ -> [0, 1, 2, 2, 1, 0, 0, 0, 1]

  4. Modify the Count Array to Store Cumulative Counts

    • Traverse the count array:
      • countArray[1] += countArray[0] -> [0, 1, 2, 2, 1, 0, 0, 0, 1]
      • countArray[2] += countArray[1] -> [0, 1, 3, 2, 1, 0, 0, 0, 1]
      • countArray[3] += countArray[2] -> [0, 1, 3, 5, 1, 0, 0, 0, 1]
      • countArray[4] += countArray[3] -> [0, 1, 3, 5, 6, 0, 0, 0, 1]
      • countArray[5] += countArray[4] -> [0, 1, 3, 5, 6, 6, 0, 0, 1]
      • countArray[6] += countArray[5] -> [0, 1, 3, 5, 6, 6, 6, 0, 1]
      • countArray[7] += countArray[6] -> [0, 1, 3, 5, 6, 6, 6, 6, 1]
      • countArray[8] += countArray[7] -> [0, 1, 3, 5, 6, 6, 6, 6, 7]

  5. Build the Output Array

    • Traverse the input array in reverse order: {4, 2, 2, 8, 3, 3, 1}
    • Place each element in the output array:
      • outputArray[countArray[1] - 1] = 1 -> [1, 0, 0, 0, 0, 0, 0]; countArray[1]-- -> [0, 0, 3, 5, 6, 6, 6, 6, 7]
      • outputArray[countArray[3] - 1] = 3 -> [1, 0, 0, 0, 3, 0, 0]; countArray[3]-- -> [0, 0, 3, 4, 6, 6, 6, 6, 7]
      • outputArray[countArray[3] - 1] = 3 -> [1, 0, 0, 3, 3, 0, 0]; countArray[3]-- -> [0, 0, 3, 3, 6, 6, 6, 6, 7]
      • outputArray[countArray[8] - 1] = 8 -> [1, 0, 0, 3, 3, 0, 8]; countArray[8]-- -> [0, 0, 3, 3, 6, 6, 6, 6, 6]
      • outputArray[countArray[2] - 1] = 2 -> [1, 0, 2, 3, 3, 0, 8]; countArray[2]-- -> [0, 0, 2, 3, 6, 6, 6, 6, 6]
      • outputArray[countArray[2] - 1] = 2 -> [1, 2, 2, 3, 3, 0, 8]; countArray[2]-- -> [0, 0, 1, 3, 6, 6, 6, 6, 6]
      • outputArray[countArray[4] - 1] = 4 -> [1, 2, 2, 3, 3, 4, 8]; countArray[4]-- -> [0, 0, 1, 3, 5, 6, 6, 6, 6]

  6. Copy the Output Array Back to the Input Array

    • array1 = {1, 2, 2, 3, 3, 4, 8}

Code

java
public class Solution {

    // Function to perform Counting Sort
    public void countingSort(int[] array) {
        // Find the maximum value in the array
        int max = findMax(array);

        // Create a count array to store the count of each unique element
        int[] countArray = new int[max + 1];

        // Initialize count array with all zeros
        for (int i = 0; i < countArray.length; i++) {
            countArray[i] = 0;
        }

        // Store the count of each element in the count array
        for (int i = 0; i < array.length; i++) {
            countArray[array[i]]++;
        }

        // Modify the count array by adding the previous counts
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        // Create an output array to store the sorted elements
        int[] outputArray = new int[array.length];

        // Build the output array using the count array
        for (int i = array.length - 1; i >= 0; i--) {
            outputArray[countArray[array[i]] - 1] = array[i];
            countArray[array[i]]--;
        }

        // Copy the sorted elements back into the original array
        for (int i = 0; i < array.length; i++) {
            array[i] = outputArray[i];
        }
    }

    // Helper function to find the maximum value in the array
    private static int findMax(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }

    // Main method to test Counting Sort with 3 examples
    public static void main(String[] args) {
        // Example 1
        int[] array1 = {4, 2, 2, 8, 3, 3, 1};
        Solution sol = new Solution();
        sol.countingSort(array1);
        System.out.println("Sorted array 1: " + java.util.Arrays.toString(array1));

        // Example 2
        int[] array2 = {10, 7, 8, 9, 1, 5};
        sol.countingSort(array2);
        System.out.println("Sorted array 2: " + java.util.Arrays.toString(array2));

        // Example 3
        int[] array3 = {3, 6, 4, 2, 1, 7, 5, 8};
        sol.countingSort(array3);
        System.out.println("Sorted array 3: " + java.util.Arrays.toString(array3));
    }
}

Complexity Analysis

Time Complexity

Overall time complexity:

Space Complexity

Overall space complexity:

Real-Time Applications of Counting Sort

🤖 Don't fully get this? Learn it with Claude

Stuck on Counting Sort Algorithm? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Counting Sort Algorithm** (DSA) and want to truly understand it. Explain Counting Sort Algorithm from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Counting Sort Algorithm** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Counting Sort Algorithm** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Counting Sort Algorithm** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Introduction to Linear Sorting AlgRadix Sort Algorithm →