Counting Sort Algorithm Explained with Examples

The Counting Sort Algorithm is a non- comparable sorting algorithm that counts how many times each distinct element appears in the input array. The location of each element in the sorted output array is then ascertained using the count. When the range of the input values is short and known, this approach performs well.

Unlike comparison-based sorting algorithms like QuickSort or MergeSort, Counting Sort leverages the range of input values to sort elements directly, achieving a time complexity of O(n+k), where n is the number of elements and k is the range of input values.

Important Concepts and Characteristics

To learn Counting Sort, one must be conversant with its fundamental ideas:

• Non-Comparative Sorting: Counting Sort does not compare elements against each other. Instead, it counts the occurrences of each unique element and uses this information to determine their positions in the sorted array.
• Integer-Based Sorting: The Counting Sort Algorithm is specifically designed for sorting integers or data that can be mapped to integers. It is not appropriate for direct sorting of strings or floating-point integers.
• Stable Sorting Algorithm: Because Counting Sort is a Stable Sorting Algorithm, two elements with the same value will have the same relative order in the output as they had in the input. This is an important feature when the original order of equal elements must be preserved.
• Auxiliary Space: The algorithm for counting sort requires additional memory space to store the counts of each element and to construct the sorted output array. The amount of auxiliary space depends on the range of input values.

Counting Sort may be modified to accommodate a greater range of data types and unusual circumstances, even though its primary purpose is to sort non-negative integers. The following are typical modifications and things to think about:

1. Adapting for Negative Numbers

Because array indices cannot be negative, counting sort by default only operates with non-negative numbers. On the other hand, you can shift all values to be non-negative before sorting arrays that include negative numbers:

• Find the minimum value in the input array.
• Offset all elements by subtracting the minimum value, making the smallest element zero.
• Apply counting sort as usual on the shifted values.
• Reverse the offset in the sorted output to restore original values.

As long as the whole range (max-min) is not too big, this method enables counting sort to handle negative numbers well.

2. Sorting Non-Numeric Data by Mapping to Integers

Counting sort can be extended to non-integer data types by mapping each item to an integer key:

• Characters: Make use of their Unicode or ASCII values as keys.
• Objects: To use as the sorting key, extract an integer attribute (such as a price, ID, or timestamp).
• Strings or Custom Types: Map to integers if a logical, finite mapping exists.

Counting the integer keys after mapping. Maintain references or recreate the sorted output using auxiliary data structures if the original data must be kept. 

3. Sorting Complex Objects While Preserving Stability

The stability of the counting sort guarantees that items with equal keys maintain their initial relative order when sorting objects with integer keys. When supplementary qualities are important or for multi-level sorting, this is very helpful.

• Extract the key for sorting.
• Apply counting sort, placing each object based on its key.
• To preserve stability, make sure reverse traversal is used, just like in the conventional algorithm.

4. Limitations with Floating-Point Numbers and Arbitrary Data

Without a definite and clear integer mapping, counting sort is not really suitable for floating-point numbers or other data types in general. One- to-one mapping of floating-point numbers to the indices of an array can lead to the loss of accuracy or excessive space usage. If at all feasible, preprocess the data into sortable integer categories or take into account different sorting techniques for such data.

5. Handling Large or Sparse Ranges

If the range of keys is very large or sparse (e.g., sorting large IDs or dates), using a traditional count array may be memory-inefficient. In these cases:

• If the key space is sparse, think about counting occurrences using a hash map.
• Determine whether counting sort is still feasible or whether another method is better.

Bottom Line

Counting Sort is capable of dealing with negative values and non-numeric data only with preprocessing and mapping to integers, while preserving stability for complex objects. Nevertheless, its success is entirely based on having a small and dense value range; large, sparse, or floating-point ranges very quickly make it memory-inefficient and not feasible.

The counting sort algorithm uses the frequency of each value to sort an array of non-negative integers. When the range of input values is not much more than the number of elements, the process is reliable, effective, and very helpful.

Step-by-Step Algorithm

1. Find the Maximum Value
   Identify the maximum value (max) in the input array. This determines the size of the auxiliary count array.
2. Initialize the Count Array
   Create a count array (count[]) of size max + 1 and initialize all entries to zero.
3. Count Occurrences
   Traverse the input array and increment the count at the index corresponding to each element's value.
4. Compute Cumulative Counts (Prefix Sum)
   Modify the count array so that each position contains the sum of previous counts. This cumulative count determines the position of each element in the output array and ensures stability.
   For every index i from 1 to max:
   count[i] = count[i] + count[i - 1]
5. Build the Output Array (Stable Placement)
   Traverse the input array in reverse order. For each element:
   
   • Use the cumulative count to determine its correct position in the output array.
   • Place the element at output[count[element] - 1] and decrement count[element] by 1.
6. Copy Output Array to Input (Optional)
   To complete the sort in-place, copy the sorted elements from the output array back into the original input array.

Why Use the Cumulative Count?

The cumulative count (prefix sum) is crucial for maintaining the stability of the sort. It ensures that for elements with the same value, their relative order from the original array is preserved in the sorted output.

Let's follow through a specific example, monitoring each step and the status of all important arrays, in order to fully comprehend how counting sort handles data.

Example Input

Suppose we want to sort the following array:

Input Array:

arr = [6, 1, 7, 1, 3, 5, 4]

Step 1: Find the Maximum Value

First, determine the largest value in the array.

Maximum value (max) = 7

Step 2: Initialize the Counting Array

Make a counting array that is started with zeros and has a size of max + 1 (to encompass 0 through 7).

Counting Array:

[0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Count Occurrences

Go through the input array and increment the count for each value.

After counting all elements:

Counting Array:

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

Step 4: Compute Cumulative Counts

Transform the counting array so that each element at index i contains the sum of counts up to i. This helps determine the final position of each value.

Final Cumulative Counting Array:

[0, 2, 2, 3, 4, 5, 6, 7]

Step 5: Build the Output Array (Stable Placement)

To guarantee stability, now process the input array in reverse order. For every component:

• Look up its cumulative count in the counting array
• Place it in the output array at position count[element] - 1
• Decrement its count in the counting array

Final Output Array

[1, 1, 3, 4, 5, 6, 7]

Step 6: Copy Output Array to Input (Optional)

Copy the sorted output back to the original array if in-place sorting is required.

What Did Each Step Achieve?

• We can determine the quantity of each value by counting occurrences.
• Each value's final sorted position is determined by cumulative counts.
• By traversing the array from right to left, we make sure the sorting is stable, i. e., the relative order of items with the same key values is preserved.

Quick Reference: Main Steps

1. Get the maximum value in the input array.
2. Create the counting array filled with zeroes.
3. Count occurrences for each value.
4. Calculate cumulative counts so that the positions can be determined.
5. Place elements into the output array using cumulative counts (reverse for stability).
6. Copy output back if needed.

This walkthrough demonstrates exactly how counting sort processes data, step by step, so you can visualize and understand every stage of the algorithm.

Here’s the Pseudocode Implementation of the counting sort algorithm:

function CountingSort(input, k)
    count ← array of k+1 zeros
    output ← array of same length as input

    for i = 0 to length(input) - 1 do
        j = input[i]
        count[j] = count[j] + 1

    for i = 1 to k do
        count[i] = count[i] + count[i-1]

    for i = length(input) - 1 downto 0 do
        j = input[i]
        count[j] = count[j] - 1
        output[count[j]] = input[i]

    return output

Below are concise, well-commented implementations of counting sort in Python, Java, C, and C++. Each implementation maintains stability by using the cumulative count and reverse traversal.

Python Implementation

def counting_sort(arr):
    if not arr:
        return arr

    max_val = max(arr)
    count = [0] * (max_val + 1)
    output = [0] * len(arr)

    # Count occurrences
    for num in arr:
        count[num] += 1

    # Compute cumulative count
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Build output array (reverse for stability)
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    return output

# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("Sorted array:", sorted_arr)

Explanation

This code sorts numbers using the Counting Sort method.

• First, it finds the largest number in the list to know how many positions are needed in the count array.
• Then, it counts how many times each number appears in the input list.
• Next, it converts these counts into positions that tell where each number should go in the sorted list.
• After that, it places each number into its correct position in the output list, starting from the end, to keep the order of duplicate numbers.
• Finally, it returns the sorted list.

Output

Sorted array: [1, 2, 2, 3, 3, 4, 8]

Java Implementation

public static void countingSort(int[] arr) {
    if (arr.length == 0)
        return;

    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    int[] output = new int[arr.length];

    // Count occurrences
    for (int num : arr)
        count[num]++;

    // Compute cumulative count
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

    // Build output array (reverse for stability)
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Copy back to original array
    System.arraycopy(output, 0, arr, 0, arr.length);
}

C Implementation

void countingSort(int array[], int size) {
    int max = array[0];

    for (int i = 1; i < size; i++)
        if (array[i] > max)
            max = array[i];

    int count[max + 1];
    int output[size];

    // Initialize count array
    for (int i = 0; i <= max; i++)
        count[i] = 0;

    // Count occurrences
    for (int i = 0; i < size; i++)
        count[array[i]]++;

    // Compute cumulative count
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

    // Build output array (reverse for stability)
    for (int i = size - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // Copy back to original array
    for (int i = 0; i < size; i++)
        array[i] = output[i];
}

C++ Implementation

void countingSort(int array[], int size) {
    int max = array[0];

    for (int i = 1; i < size; i++)
        if (array[i] > max)
            max = array[i];

    std::vector<int> count(max + 1, 0);
    std::vector<int> output(size);

    // Count occurrences
    for (int i = 0; i < size; i++)
        count[array[i]]++;

    // Compute cumulative count
    for (int i = 1; i <= max; i++)
        count[i] += count[i - 1];

    // Build output array (reverse for stability)
    for (int i = size - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // Copy back to original array
    for (int i = 0; i < size; i++)
        array[i] = output[i];
}

Key Implementation Notes

• Stability: The relative order of equal items is maintained during placement due to reverse traversal.
• Cumulative Count: This stage is crucial for figuring out the right index for every value in the output array.
• Auxiliary Arrays: The algorithm's proper and stable operation depends on both the count and output arrays. 

Readers may safely construct a counting sort in their favourite programming language by following this comprehensive method and consulting these implementations, completely comprehending each step and its function.

Although counting sort is well known for its effectiveness under certain conditions, the link between the input size (n) and the range of values (k) has a significant impact on its performance. A thorough examination of its computational complexity under various conditions is provided below.

Time Complexity

Counting Sort operates in O(n + k) time, where:

• n = number of elements to sort
• k = the range of possible input values (maximum value - minimum value + 1)

Best Case

• Scenario: The range k is very small and close to n (e.g., sorting exam scores from 0–100 for a class of 100 students).
• Complexity: O(n + k) ≈ O(n)
• Explanation: How long it takes to finish all operations, such as counting occurrences, computing cumulative counts, and building the output, depends on the total number of components and the narrow range. When k is constant or much less than n, the overhead from the counting array is negligible.

Average Case

• Scenario: The range k is moderately larger than n, but not excessively so.
• Complexity: O(n + k)
• Explanation: Regardless of the distribution or order of input, the algorithm always processes every input element and every potential value in the range. The average case is therefore still O(n + k).

Worst Case

• Scenario: The range k is much larger than n, such as sorting a small array with values that span from 1 to 1,000,000.
• Complexity: O(n + k)
• Explanation: The largest amount of time spent comes from the need to initialize and work with a counting array of size k. The method can drop to only O(k) in cases where k n and hence becomes a worse choice than comparison-based sorts for large values of k.

Key Point:

The time complexity of Counting Sort is independent of the input's beginning order (ascending, descending, or random), in contrast to several other sorting algorithms. It depends just on n and k.

Space Complexity

• Overall Complexity: O(n + k)
  
  • O(k) space for the counting array
  • O(n) space for the output array

Implications:

• Space use is effective when k is small or near n.
• Counting Sort is not viable for big or sparse ranges when k is significantly larger than n since the counting array can use a lot of memory.

Summary Table

• n = number of elements to sort
• k = range of input values

Practical Considerations

• Linear Performance: Only when k = O(n), which indicates that the range of values is not much greater than the number of elements, is counting sort really linear (O(n)).
• Space Efficiency: When selecting Counting Sort, always take into account the range in relation to the size of the dataset because a large k results in significant memory utilization. 
• Input Distribution: The distribution or order of input values does not affect the algorithm’s time or space complexity.

This analysis provides a clear, scenario-based understanding of Counting Sort’s computational complexity, helping readers assess when the algorithm is the optimal choice.

Here are the advantages of the counting sort algorithm:

1. Linear Time Complexity

One of the biggest strengths of the Counting Sort Algorithm is its linear time complexity when the range of input values (denoted as k) is close to the number of elements (n). The algorithm runs in O(n + k) time, which makes it significantly faster than comparison-based algorithms like Merge Sort or QuickSort in the right conditions. 

2. Stable Sorting

The Counting Sort Algorithm is a stable sorting algorithm, which means that elements with the same value retain their relative positions from the original input. This is particularly useful when sorting data that is already organized by a secondary attribute. 

3. Simple and Easy to Implement

Another major advantage of the algorithm for counting sort is its simplicity. The core idea counts the occurrences of each value and uses those counts to place elements in the correct position is easy to understand and implement. 

Counting sort is a powerful algorithm, but its efficiency and practicality depend on meeting certain conditions. Understanding these requirements, as well as the limitations, ensures you choose the right sorting technique for your data.

When Counting Sort is Most Effective

Counting sort delivers optimal performance under the following conditions:

• Non-Negative Integer Inputs:
  Counting sort is designed to work with non-negative integers or data that can be directly mapped to non-negative integers. Each unique value is used as an index in the counting array, so negative numbers or non-integer values are not supported in the standard approach.
• Known and Limited Range (k):
  When the range of potential input values (k) is not appreciably greater than the total number of elements to be sorted (n), the algorithm performs at its best. Counting sort retains its linear time and space complexity within a short, defined range.
• Range Comparable to Input Size:
  When the range of values is near the number of elements, counting sort performs exceptionally well. For instance, it is preferable to sort 1,000 exam results so that every number falls between 0 and 100.
• Stable Sorting Needed:
  The basic stability of counting sort is a significant benefit if maintaining the original order of equal elements is crucial.

Limitations and Unsuitable Scenarios

Despite its strengths, the counting sort algorithm has notable limitations:

• Inefficiency with Large or Sparse Ranges:
  The counting array gets huge and memory-inefficient if the range of input values (k) is significantly more than the number of entries (n). For example, sorting a handful of IDs that range up to a million wastes space and slows down the algorithm.
• Not Suitable for Negative Numbers or Non-Integers (Without Adaptation):
  Complex data types, floating-point values, and negative integers cannot be handled by a standard counting sort. Although there are certain adjustments (such mapping objects to integers or offsetting negative values), these might further raise complexity and space requirements.
• Range Must Be Known in Advance:
  Counting sort requires you to know the minimum and maximum values in the dataset to allocate the counting array. If the range is unknown or unbounded, the algorithm is impractical.
• High Auxiliary Space Usage:
  The counting array (size k) and the output array (size n) always need extra space for counting sort. Even with a modest input dataset, this may be costly for very broad ranges.

Special Considerations

• Handling Negative Numbers:
  By shifting all input values until the minimum value is zero, counting sort may be modified to include negative integers. For the method to continue being effective, the overall range (max-min) must still be modest.
• Sparse Data and Memory Efficiency:
  Using a counting array is memory-inefficient when there is a vast range of potential values, but only a few values are present (sparse data). Alternative methods, such as hash maps, may be useful in certain situations, albeit at the expense of the algorithm's speed and simplicity.

Summary Table: Conditions and Limitations

By understanding these conditions and limitations, you can determine when a counting sort is the optimal choice and when other sorting algorithms may be more appropriate.

When you need to sort data that complies with certain restrictions, like non-negative integers within a given range, counting sort is the method that is most often recognized for its efficiency and transparency. Here are some of the most common and practical examples of where a counting sort is a good fit:

1. Sorting Small Integer Datasets

When sorting datasets with tiny, non-negative integer values and a range of potential values that is not much more than the number of elements, counting sort works quite well. It is therefore perfect for:

• Sorting exam or test scores (e.g., scores from 0 to 100)
• Organizing product IDs or inventory codes that fall within a known range
• Arranging event timestamps, such as days, months, or years, when the range is limited

2. Frequency Analysis and Histogram Construction

The core mechanism of counting sort, tallying the frequency of each unique value, makes it a natural fit for building histograms and frequency tables. Understanding the distribution of discrete values is crucial in data analysis and visualization, where this is especially helpful.

3. Sorting Characters by ASCII or Unicode Values

Characters or strings of single characters may be effectively sorted using counting sort, as characters are represented by integer values (such as ASCII codes). This is especially beneficial in:

• Text processing applications
• Compiler design and lexical analysis, where tokens (characters) are sorted or grouped
• Alphabetizing lists of characters

4. Subroutine in Radix Sort

Radix sort employs counting sort as an essential subroutine mainly due to its linear time execution and stability. Counting sort is a major tool in a radix sort arsenal to sort the numbers through each digit while preserving the relative order of the same digits at every step.

5. Efficient Sorting in Survey and Polling Data

Counting sort provides a quick and compact method of organizing and analyzing survey replies or poll results that are restricted to a specific number of integer alternatives (e.g., ratings from 1 to 5).

Summary Table: Common Use Cases for Counting Sort

By leveraging counting sort in these scenarios, you can achieve stable, linear-time sorting and efficient data analysis, provided the data meets the algorithm’s requirements for value range and type.

Counting Sort Algorithm is a powerful linear-time sorting algorithm best suited for sorting integers within a known and limited range. To put elements in their ordered places, it employs a counting technique. It is a great option for situations like radix-based sorting, creating histograms, or arranging categorical numerical data because of its speed and reliability.

However, it isn't always the ideal option for all applications due to its high space demand and restriction to integer sorting. When used in the right context, the algorithm for counting sort delivers both simplicity and performance.

Points to Remember 

1. Counting Sort is Non-Comparative
   It does not make elemental comparisons. Rather, it makes direct use of locations and counts occurrences.
2. Works Best When Range is Small
   Its efficiency depends on the relationship between n (elements) and k (range).
   Best case: k ≈ n.
3. Time Complexity is O(n + k)
   Faster than comparison sorts when the range of values is limited.
4. It Is a Stable Sorting Algorithm
   Equal elements retain their original relative order, crucial for radix sort and multi-key sorting.
5. Space Trade-off Is the Main Limitation
   It is not appropriate for big or sparse ranges since it requires more memory for the count array and output array.

1. When is Counting Sort most efficient?

When the range of the input values (k) is quite small or almost equals the number of items (n), a counting sort is very efficient. It then operates in linear time, thus beating classical algorithms such as QuickSort in performance.

2. Can Counting Sort handle negative numbers?

By default, Counting Sort only handles non-negative integers. However, it can be adapted for negative numbers by offsetting all elements so the minimum value becomes zero before applying the algorithm.

3. Is Counting Sort a stable sorting algorithm?

Yes, Counting Sort is stable. It preserves the relative order of elements with the same value, which is essential when sorting items that are already partially ordered or have secondary attributes.

4. Why is Counting Sort not comparison-based?

Counting Sort does not internally compare one element with another. Instead, it exploits the values of elements to figure out how many times each one appears and, therefore, where they map in the final sorted sequence. Thus, it is not subjected to the O(n log n) lower bound of comparison-based sorting algorithms.

5. Can I use Counting Sort for floating-point numbers or strings?

Not automatically. Counting Sort can only be operative with integers or data that can be transformed to integers (e. g., characters via ASCII codes). To incorporate strings or float numbers, you will have to convert them first into sortable integers.

6. What is the space complexity of Counting Sort?

The space complexity is O(k + n), where k determines the range of possible input values while n is the number of elements. The additional space is occupied by the count array and the output array.

7. How is Counting Sort used in Radix Sort?

Counting Sort is often used as a stable sorting step in Radix Sort. It sorts digits at each place value from least to most significant, ensuring overall correctness and efficiency of the radix-based sorting approach.