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 O(n + k), 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.

2. 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.

3. 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.

4. 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.

5. 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.

• (5.1). For index i = 6,
  • Update outputArray[ countArray[ inputArray[6] ] – 1 ] = inputArray[6]
  • Also, update countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

• (5.2). For index i = 5,
  • Update outputArray[ countArray[ inputArray[5] ] – 1 ] = inputArray[5]
  • Also, update countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

• (5.3). For index i = 4,
  • Update outputArray[ countArray[ inputArray[4] ] – 1 ] = inputArray[4] ]
  • Also, update countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

• (5.4). For index i = 3,
  • Update outputArray[ countArray[ inputArray[3] ] – 1 ] = inputArray[3]
  • Also, update countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

• (5.5). For index i = 2,
  • Update outputArray[ countArray[ inputArray[2] ] – 1 ] = inputArray[2]
  • Also, update countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

• (5.6). For index i = 1,
  • Update outputArray[ countArray[ inputArray[1] ] – 1 ] = inputArray[1]
  • Also, update countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

• (5.7). For index i = 0,
  • Update outputArray[ countArray[ inputArray[0] ] – 1 ] = inputArray[0]
  • Also, update countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

6. 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

Complexity Analysis

Time Complexity

• Finding the maximum value: O(n)
• Creating and initializing the count array: O(k), where k is the range of the input values
• Counting the frequency of elements: O(n)
• Calculating the cumulative sum of count array: O(k)
• Building the output array: O(n)
• Copying the output array: O(n)

Overall time complexity: O(n + k)

Space Complexity

• Count array: O(k)
• Output array: O(n)

Overall space complexity: O(n + k)

Real-Time Applications of Counting Sort

• Sorting Exam Scores: Efficiently sorts large datasets of exam scores that fall within a fixed range.
• Voting Count: Tallying votes where each candidate can be assigned an integer value.
• Gene Sequencing: Sorting short sequences of nucleotides (A, C, G, T) which can be mapped to integers.
• Data Normalization: Sorting and normalizing data values that fall within a known range.
• Distribution Counting: Counting and sorting objects or events within specific categories or bins.
• Event Scheduling: Organizing events or tasks based on start times represented as integers.
• Inventory Management: Sorting items based on quantities within a fixed range, such as stock levels.