Sorting Algorithms- 5 - Algorithms - Computer Science Engineering (CSE)

Counting Sort

Counting sort is a non-comparison based sorting technique that works when input keys lie in a known, limited range. The algorithm counts the number of occurrences of each distinct key value. Using these counts, it computes positions for each element in the output array and places them accordingly. Counting sort is often used as a subroutine in other algorithms such as radix sort.

Basic idea and step-by-step example

Consider input values in the range 0 to 9 for simplicity.

Input: 1, 4, 1, 2, 7, 5, 2

1. Create a count array indexed by the possible key values and initialise all counts to zero.
2. Scan the input and increment the count for each key.
3. Modify the count array so that each element at index i contains the number of elements less than or equal to i. This is done by replacing count[i] by count[i] + count[i-1] for i from 1 to k-1 (k is range size).
4. Build the output array by traversing the input in reverse (to preserve stability). For each element x, place it at position count[x] - 1 in the output and decrement count[x].
5. Copy the output array back to the input array if an in-place result is required.

Apply these steps to the example:

Step 1: Initial counts (after scanning input) Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 2 0 1 1 0 1 0 0 Step 2: Modify to accumulate counts (prefix sum) Index: 0 1 2 3 4 5 6 7 8 9 Count: 0 2 4 4 5 6 6 7 7 7 Step 3: Build output by processing input in reverse (for stability) Process input (reversed): 2,5,7,2,1,4,1 Place 2 at index count[2]-1 = 3 => output[3] = 2; count[2]-- Place 5 at index count[5]-1 = 5 => output[5] = 5; count[5]-- Place 7 at index count[7]-1 = 6 => output[6] = 7; count[7]-- Place 2 at index count[2]-1 = 1 => output[1] = 2; count[2]-- Place 1 at index count[1]-1 = 1 => output[1] = 1; (after the prior placement output indices adjust by counts) ... Final sorted output: 1, 1, 2, 2, 4, 5, 7

Properties

• Time complexity: O(n + k), where n is number of elements and k is the range of distinct key values.
• Auxiliary space: O(n + k) for the output array and count array.
• Stability: Counting sort can be implemented as a stable sort by processing the input from right to left when building the output.
• Comparison-free: It does not compare elements; it counts occurrences.
• Best used when: k is not significantly larger than n (i.e., range is reasonably small relative to number of items).

Handling negative numbers

Counting sort as described uses array indices corresponding to keys, so negative keys need an offset. Find the minimum value min and maximum value max, compute range = max - min + 1, and then shift each element by subtracting min when indexing the count array. After sorting, shift back if necessary.

Implementations

The following implementations demonstrate counting sort for characters (byte/ASCII) and for integer arrays including negative numbers. Each language block contains the corresponding source and any contributor note preserved.

• C++ (characters, ASCII)

  <!-- C++ Program for counting sort --> #include <bits/stdc++.h> #include <string.h> using namespace std; #define RANGE 255 // The main function that sort // the given string arr[] in // alphabetical order void countSort(char arr[]) { // The output character array // that will have sorted arr char output[strlen(arr)]; // Create a count array to store count of individual // characters and initialize count array as 0 int count[RANGE + 1], i; memset(count, 0, sizeof(count)); // Store count of each character for (i = 0; arr[i]; ++i) ++count[arr[i]]; // Change count[i] so that count[i] now contains actual // position of this character in output array for (i = 1; i <= RANGE; ++i) count[i] += count[i - 1]; // Build the output character array for (i = 0; arr[i]; ++i) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } /* For Stable algorithm for (i = sizeof(arr)-1; i>=0; --i) { output[count[arr[i]]-1] = arr[i]; --count[arr[i]]; } For Logic : See implementation */ // Copy the output array to arr, so that arr now // contains sorted characters for (i = 0; arr[i]; ++i) arr[i] = output[i]; } // Driver code int main() { char arr[] = "edurev"; countSort(arr); cout << "Sorted character array is " << arr; return 0; } // This code is contributed by rathbhupendra

• C (characters, ASCII)

  <!-- C Program for counting sort --> #include <stdio.h> #include <string.h> #define RANGE 255 // The main function that sort the given string arr[] in // alphabatical order void countSort(char arr[]) { // The output character array that will have sorted arr char output[strlen(arr)]; // Create a count array to store count of inidividul // characters and initialize count array as 0 int count[RANGE + 1], i; memset(count, 0, sizeof(count)); // Store count of each character for (i = 0; arr[i]; ++i) ++count[arr[i]]; // Change count[i] so that count[i] now contains actual // position of this character in output array for (i = 1; i <= RANGE; ++i) count[i] += count[i - 1]; // Build the output character array for (i = 0; arr[i]; ++i) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } /* For Stable algorithm for (i = sizeof(arr)-1; i>=0; --i) { output[count[arr[i]]-1] = arr[i]; --count[arr[i]]; } */ // Copy the output array to arr, so that arr now // contains sorted characters for (i = 0; arr[i]; ++i) arr[i] = output[i]; } // Driver program to test above function int main() { char arr[] = "edurev"; // "applepp"; countSort(arr); printf("Sorted character array is %sn", arr); return 0; }

• Java (characters, ASCII)

  // Java implementation of Counting Sort class CountingSort { void sort(char arr[]) { int n = arr.length; // The output character array that will have sorted arr char output[] = new char[n]; // Create a count array to store count of inidividul // characters and initialize count array as 0 int count[] = new int[256]; for (int i = 0; i < 256; ++i) count[i] = 0; // store count of each character for (int i = 0; i < n; ++i) ++count[arr[i]]; // Change count[i] so that count[i] now contains actual // position of this character in output array for (int i = 1; i <= 255; ++i) count[i] += count[i - 1]; // Build the output character array // To make it stable we are operating in reverse order. for (int i = n - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } // Copy the output array to arr, so that arr now // contains sorted characters for (int i = 0; i < n; ++i) arr[i] = output[i]; } // Driver method public static void main(String args[]) { CountingSort ob = new CountingSort(); char arr[] = { 'g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's' }; ob.sort(arr); System.out.print("Sorted character array is "); for (int i = 0; i < arr.length; ++i) System.out.print(arr[i]); } } /*This code is contributed by Rajat Mishra */

• Python3 (characters, ASCII)

  # Python program for counting sort # The main function that sort the given string arr[] in # alphabetical order def countSort(arr): # The output character array that will have sorted arr output = [0 for i in range(len(arr))] # Create a count array to store count of inidividul # characters and initialize count array as 0 count = [0 for i in range(256)] # For storing the resulting answer since the # string is immutable ans = ["" for _ in arr] # Store count of each character for i in arr: count[ord(i)] += 1 # Change count[i] so that count[i] now contains actual # position of this character in output array for i in range(256): count[i] += count[i-1] # Build the output character array for i in range(len(arr)): output[count[ord(arr[i])]-1] = arr[i] count[ord(arr[i])] -= 1 # Copy the output array to arr, so that arr now # contains sorted characters for i in range(len(arr)): ans[i] = output[i] return ans # Driver program to test above function arr = "edurev" ans = countSort(arr) print("Sorted character array is % s" %("".join(ans))) # This code is contributed by Nikhil Kumar Singh

• C# (characters, ASCII)

  // C# implementation of Counting Sort using System; class GFG { static void countsort(char[] arr) { int n = arr.Length; // The output character array that // will have sorted arr char[] output = new char[n]; // Create a count array to store // count of inidividul characters // and initialize count array as 0 int[] count = new int[256]; for (int i = 0; i < 256; ++i) count[i] = 0; // store count of each character for (int i = 0; i < n; ++i) ++count[arr[i]]; // Change count[i] so that count[i] // now contains actual position of // this character in output array for (int i = 1; i <= 255; ++i) count[i] += count[i - 1]; // Build the output character array // To make it stable we are operating in reverse order. for (int i = n - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } // Copy the output array to arr, so // that arr now contains sorted // characters for (int i = 0; i < n; ++i) arr[i] = output[i]; } // Driver method public static void Main() { char[] arr = { 'g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's' }; countsort(arr); Console.Write("Sorted character array is "); for (int i = 0; i < arr.Length; ++i) Console.Write(arr[i]); } } // This code is contributed by Sam007.

• PHP (characters, ASCII)

  <?php // PHP Program for counting sort $RANGE = 255; // The main function that sort // the given string arr[] in // alphabatical order function countSort($arr) { global $RANGE; // The output character array // that will have sorted arr $output = array(strlen($arr)); $len = strlen($arr); // Create a count array to // store count of inidividul // characters and initialize // count array as 0 $count = array_fill(0, $RANGE + 1, 0); // Store count of // each character for($i = 0; $i < $len; ++$i) ++$count[ord($arr[$i])]; // Change count[i] so that // count[i] now contains // actual position of this // character in output array for ($i = 1; $i <= $RANGE; ++$i) $count[$i] += $count[$i - 1]; // Build the output // character array // To make it stable we are operating // in reverse order. for ($i = $len-1; $i >= 0 ; $i--) { $output[$count[ord($arr[$i])] - 1] = $arr[$i]; --$count[ord($arr[$i])]; } // Copy the output array to // arr, so that arr now // contains sorted characters for ($i = 0; $i < $len; ++$i) $arr[$i] = $output[$i]; return $arr; } // Driver Code $arr = "edurev"; // "applepp"; $arr = countSort($arr); echo "Sorted character array is " . $arr; // This code is contributed by mits ?>

• Javascript (characters, ASCII)

  <script> // Javascript implementation of Counting Sort function sort(arr) { var n = arr.length; // The output character array that will have sorted arr var output = Array.from({length: n}, (_, i) => 0); // Create a count array to store count of inidividul // characters and initialize count array as 0 var count = Array.from({length: 256}, (_, i) => 0); // store count of each character for (var i = 0; i < n; ++i) ++count[arr[i].charCodeAt(0)]; // Change count[i] so that count[i] now contains actual // position of this character in output array for (var i = 1; i <= 255; ++i) count[i] += count[i - 1]; // Build the output character array // To make it stable we are operating in reverse order. for (var i = n - 1; i >= 0; i--) { output[count[arr[i].charCodeAt(0)] - 1] = arr[i]; --count[arr[i].charCodeAt(0)]; } // Copy the output array to arr, so that arr now // contains sorted characters for (var i = 0; i < n; ++i) arr[i] = output[i]; return arr; } // Driver method var arr = [ 'g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's' ]; arr = sort(arr); document.write("Sorted character array is "); for (var i = 0; i < arr.length; ++i) document.write(arr[i]); // This code is contributed by shikhasingrajput </script>

Implementations for integer arrays including negative numbers

• C++ (integers, handles negatives)

  // Counting sort which takes negative numbers as well #include <algorithm> #include <iostream> #include <vector> using namespace std; void countSort(vector<int>& arr) { int max = *max_element(arr.begin(), arr.end()); int min = *min_element(arr.begin(), arr.end()); int range = max - min + 1; vector<int> count(range), output(arr.size()); for (int i = 0; i < arr.size(); i++) count[arr[i] - min]++; for (int i = 1; i < count.size(); i++) count[i] += count[i - 1]; for (int i = arr.size() - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (int i = 0; i < arr.size(); i++) arr[i] = output[i]; } void printArray(vector<int>& arr) { for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; cout << "
  "; } int main() { vector<int> arr = { -5, -10, 0, -3, 8, 5, -1, 10 }; countSort(arr); printArray(arr); return 0; }

• Java (integers, handles negatives)

  // Counting sort which takes negative numbers as well import java.util.*; class GFG { static void countSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); int range = max - min + 1; int count[] = new int[range]; int output[] = new int[arr.length]; for (int i = 0; i < arr.length; i++) { count[arr[i] - min]++; } for (int i = 1; i < count.length; i++) { count[i] += count[i - 1]; } for (int i = arr.length - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (int i = 0; i < arr.length; i++) { arr[i] = output[i]; } } static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(""); } // Driver code public static void main(String[] args) { int[] arr = { -5, -10, 0, -3, 8, 5, -1, 10 }; countSort(arr); printArray(arr); } } // This code is contributed by princiRaj1992

• Python3 (integers, handles negatives)

  # Python program for counting sort # which takes negative numbers as well # The function that sorts the given arr[] def count_sort(arr): max_element = int(max(arr)) min_element = int(min(arr)) range_of_elements = max_element - min_element + 1 # Create a count array to store count of individual # elements and initialize count array as 0 count_arr = [0 for _ in range(range_of_elements)] output_arr = [0 for _ in range(len(arr))] # Store count of each element for i in range(0, len(arr)): count_arr[arr[i]-min_element] += 1 # Change count_arr[i] so that count_arr[i] now contains actual # position of this element in output array for i in range(1, len(count_arr)): count_arr[i] += count_arr[i-1] # Build the output array for i in range(len(arr)-1, -1, -1): output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] count_arr[arr[i] - min_element] -= 1 # Copy the output array to arr, so that arr now # contains sorted elements for i in range(0, len(arr)): arr[i] = output_arr[i] return arr # Driver program to test above function arr = [-5, -10, 0, -3, 8, 5, -1, 10] ans = count_sort(arr) print("Sorted character array is " + str(ans))

• C# (integers, handles negatives)

  // Counting sort which takes negative numbers as well using System; using System.Collections.Generic; using System.Linq; class GFG { static void countSort(int[] arr) { int max = arr.Max(); int min = arr.Min(); int range = max - min + 1; int []count = new int[range]; int []output = new int[arr.Length]; for (int i = 0; i < arr.Length; i++) { count[arr[i] - min]++; } for (int i = 1; i < count.Length; i++) { count[i] += count[i - 1]; } for (int i = arr.Length - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (int i = 0; i < arr.Length; i++) { arr[i] = output[i]; } } static void printArray(int[] arr) { for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " "); } Console.WriteLine(""); } // Driver code public static void Main(string[] args) { int[] arr = { -5, -10, 0, -3, 8, 5, -1, 10 }; countSort(arr); printArray(arr); } } // This code is contributed by rutvik_56.

• Javascript (integers, handles negatives)

  <script> // Counting sort which takes negative numbers as well function countSort(arr) { var max = Math.max.apply(Math, arr); var min = Math.min.apply(Math, arr); var range = max - min + 1; var count = Array.from({length: range}, (_, i) => 0); var output = Array.from({length: arr.length}, (_, i) => 0); for (i = 0; i < arr.length; i++) { count[arr[i] - min]++; } for (i = 1; i < count.length; i++) { count[i] += count[i - 1]; } for (i = arr.length - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (i = 0; i < arr.length; i++) { arr[i] = output[i]; } } function printArray(arr) { for (i = 0; i < arr.length; i++) { document.write(arr[i] + " "); } document.write('<br>'); } // Driver code var arr = [ -5, -10, 0, -3, 8, 5, -1, 10 ]; countSort(arr); printArray(arr); // This code is contributed by Amit Katiyar </script>

Sample outputs

Characters example output:

Sorted character array is eeeefggkkorss

Integers (negative allowed) example output:

-10 -5 -3 -1 0 5 8 10

Notes and practical considerations

• Counting sort is efficient if the range of input values (k) is not significantly greater than the number of items (n). If k ≫ n, the auxiliary space and time to initialise the count array can make counting sort impractical.
• Counting sort is not comparison-based and runs in O(n + k) time. This can be linear in n when k = O(n).
• Counting sort uses a form of partial hashing: it maps keys to indices and counts occurrences in O(1) per item.
• Counting sort is commonly used as a stable subroutine in radix sort to sort by digits or bytes.
• To handle negative values, shift the keys by subtracting the minimum value when indexing the count array (as shown in the provided implementations).
• Counting sort is not inherently online; it requires the entire input to build counts before producing sorted output.

Stability and online behaviour

Counting sort can be implemented as a stable algorithm by filling the output array in reverse order using the cumulative counts. It is not online because it needs the full input to compute counts before output elements can be produced in sorted order.

Parallelisation and optimisation ideas

• Parallel counting: split input into chunks, compute local counts in parallel, then reduce (sum) local counts into global counts. After obtaining prefix sums on the global counts (which can be parallelised with parallel prefix-sum algorithms), each chunk can be written into its region of the output array in parallel.
• Memory trade-offs: if k is large but sparse, consider compressing the key space (coordinate compression) before counting, or use a hash map for sparse keys (but that may increase constant factors).
• Cache and locality: choose data layouts that improve cache locality; for large k, the count array may not fit cache and will be slow to access.

Exercises

• Modify the above code to sort input data in an arbitrary range from M to N.
• Is counting sort stable and is it online? Explain with reasoning and examples.
• Discuss methods to parallelise counting sort and outline their complexity and communication costs.

Snapshots