{"title":"Counting Sort","description":"","content":"Counting Sort is a non-comparison-based sorting algorithm that works by counting the frequency of each element. Instead of comparing elements, it uses the values themselves as indices to determine their correct positions in the sorted output.\n\nThis approach allows Counting Sort to achieve linear time complexity O(n + k), where k is the range of input values. It is especially efficient when the range of numbers is not significantly larger than the number of elements.\n\nHowever, Counting Sort is only applicable when the input consists of integers within a limited range, and it requires additional space to store counts.\n\nIn this chapter, you will learn how Counting Sort works step by step, how to implement it, and when it is the right choice over comparison-based sorting algorithms.\n\n---\n\n# What Is Counting Sort?\n\nCounting Sort is a **non-comparison-based** sorting algorithm. It works by counting the number of occurrences of each distinct value in the input, then using those counts to place each element directly into its correct position in the output.\n\nHere is the core idea in three sentences. First, create a count array where index i stores how many times value i appears in the input. Second, transform the count array into a cumulative (prefix sum) array, so each index now tells you where the last element with that value should go. Third, iterate through the input from right to left, placing each element at the position indicated by the cumulative count and decrementing that count.\n\nThe algorithm has three key properties:\n\n1. **Non-comparison-based**: It never compares two input elements against each other\n2. **Stable**: Equal elements appear in the output in the same relative order as the input (when implemented correctly)\n3. **Linear time**: Runs in O(n + k) where k is the range of input values\n\n\n```mermaid\nflowchart LR\n subgraph Input\n A[\"[4, 2, 2, 8, 3, 3, 1]\"]\n end\n\n subgraph Step1[\"Step 1: Count\"]\n B[\"Count how many
times each value
appears\"]\n end\n\n subgraph Step2[\"Step 2: Prefix Sum\"]\n C[\"Cumulative counts
tell positions\"]\n end\n\n subgraph Step3[\"Step 3: Place\"]\n D[\"Place elements at
correct positions\"]\n end\n\n subgraph Output\n E[\"[1, 2, 2, 3, 3, 4, 8]\"]\n end\n\n A --> B --> C --> D --> E\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#38d9a9,stroke:#000,color:#000\n style D fill:#ffa94d,stroke:#000,color:#000\n style E fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe key insight is that counting replaces comparing. Instead of determining relative order by comparing pairs of elements, we determine absolute positions by knowing exactly how many elements are smaller than each value.\n\n### Breaking the O(n log n) Barrier\n\nEvery comparison-based sorting algorithm (Merge Sort, Quick Sort, Heap Sort) must make at least O(n log n) comparisons. This is provable using a decision tree argument: with n! possible permutations of n elements, you need at least log2(n!) comparisons to distinguish between them, and log2(n!) is O(n log n).\n\nCounting Sort sidesteps this lower bound because it never compares elements. It uses the values themselves as indices into an array, extracting ordering information from the values rather than from pairwise comparisons. This is why the time complexity depends on both n (number of elements) and k (range of values) rather than just n.\n\n---\n\n# How It Works\n\nLet us walk through the algorithm step by step, then tie it together with a flowchart.\n\n### Step 1: Find the Range\n\nScan the input array to find the minimum and maximum values. The range k = max - min + 1 determines the size of the count array. If elements are all non-negative with a known maximum, you can skip the scan and use the known range.\n\n### Step 2: Count Occurrences\n\nCreate a count array of size k, initialized to all zeros. Iterate through the input and increment `count[value - min]` for each element. After this step, `count[i]` tells you exactly how many times the value `(i + min)` appears in the input.\n\n### Step 3: Compute Cumulative Counts (Prefix Sum)\n\nTransform the count array by computing a running sum from left to right. Replace each `count[i]` with the sum of all counts from index 0 through i. After this step, `count[i]` tells you how many elements have a value less than or equal to `(i + min)`. This means `count[i]` is the position (one-indexed) where the last element with value `(i + min)` should be placed in the output.\n\n### Step 4: Build the Output Array (Right to Left)\n\nCreate an output array of the same size as the input. Iterate through the input array **from right to left**. For each element, look up its cumulative count, place the element at position `count[value - min] - 1` in the output, and decrement the count. The right-to-left traversal is what makes the sort **stable**, preserving the relative order of equal elements.\n\n### Step 5: Copy Back\n\nCopy the output array back into the original array (or simply return the output array).\n\n\n```mermaid\nflowchart TD\n A[\"Start: Input Array\"] --> B[\"Find min and max values\"]\n B --> C[\"Create count array
of size (max - min + 1)\"]\n C --> D[\"Count occurrences
of each value\"]\n D --> E[\"Compute prefix sum
on count array\"]\n E --> F[\"Iterate input
RIGHT to LEFT\"]\n F --> G[\"Place element at
count[val - min] - 1\"]\n G --> H[\"Decrement
count[val - min]\"]\n H --> I{\"More
elements?\"}\n I -- Yes --> F\n I -- No --> J[\"Output is sorted\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#ffa94d,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#38d9a9,stroke:#000,color:#000\n style F fill:#00ceff,stroke:#000,color:#000\n style G fill:#00ceff,stroke:#000,color:#000\n style H fill:#00ceff,stroke:#000,color:#000\n style I fill:#ffd43b,stroke:#000,color:#000\n style J fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe reason for the right-to-left traversal in Step 4 deserves emphasis. If two elements have the same value, the one that appears later in the input should end up at a higher index in the output. By going right to left and decrementing the count each time, we place the rightmost duplicate first (at the highest valid position), then the next one at the position just before it, and so on. This preserves the original relative order of equal elements.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class CountingSort {\n public static void countingSort(int[] arr) {\n if (arr == null || arr.length <= 1) return;\n\n // Step 1: Find the range\n int min = arr[0], max = arr[0];\n for (int val : arr) {\n if (val < min) min = val;\n if (val > max) max = val;\n }\n\n int range = max - min + 1;\n\n // Step 2: Count occurrences\n int[] count = new int[range];\n for (int val : arr) {\n count[val - min]++;\n }\n\n // Step 3: Compute prefix sums\n for (int i = 1; i < range; i++) {\n count[i] += count[i - 1];\n }\n\n // Step 4: Build output (right to left for stability)\n int[] output = new int[arr.length];\n for (int i = arr.length - 1; i >= 0; i--) {\n int idx = count[arr[i] - min] - 1;\n output[idx] = arr[i];\n count[arr[i] - min]--;\n }\n\n // Step 5: Copy back\n System.arraycopy(output, 0, arr, 0, arr.length);\n }\n}\n```\n\n```python\ndef counting_sort(arr: list[int]) -> list[int]:\n if len(arr) <= 1:\n return arr\n\n # Step 1: Find the range\n min_val = min(arr)\n max_val = max(arr)\n range_size = max_val - min_val + 1\n\n # Step 2: Count occurrences\n count = [0] * range_size\n for val in arr:\n count[val - min_val] += 1\n\n # Step 3: Compute prefix sums\n for i in range(1, range_size):\n count[i] += count[i - 1]\n\n # Step 4: Build output (right to left for stability)\n output = [0] * len(arr)\n for i in range(len(arr) - 1, -1, -1):\n idx = count[arr[i] - min_val] - 1\n output[idx] = arr[i]\n count[arr[i] - min_val] -= 1\n\n return output\n```\n\n```cpp\n#include \n#include \n\nvoid countingSort(std::vector& arr) {\n if (arr.size() <= 1) return;\n\n // Step 1: Find the range\n int minVal = *std::min_element(arr.begin(), arr.end());\n int maxVal = *std::max_element(arr.begin(), arr.end());\n int range = maxVal - minVal + 1;\n\n // Step 2: Count occurrences\n std::vector count(range, 0);\n for (int val : arr) {\n count[val - minVal]++;\n }\n\n // Step 3: Compute prefix sums\n for (int i = 1; i < range; i++) {\n count[i] += count[i - 1];\n }\n\n // Step 4: Build output (right to left for stability)\n std::vector output(arr.size());\n for (int i = arr.size() - 1; i >= 0; i--) {\n int idx = count[arr[i] - minVal] - 1;\n output[idx] = arr[i];\n count[arr[i] - minVal]--;\n }\n\n // Step 5: Copy back\n arr = output;\n}\n```\n\n```go\npackage main\n\n// Step 1: Find the range\n// Step 2: Count occurrences\n// Step 3: Compute prefix sums\n// Step 4: Build output (right to left for stability)\n// Step 5: Copy back\nfunc countingSort(arr []int) []int {\n\tif len(arr) <= 1 {\n\t\treturn arr\n\t}\n\n\t// Step 1: Find the range\n\tminVal, maxVal := arr[0], arr[0]\n\tfor _, val := range arr {\n\t\tif val < minVal {\n\t\t\tminVal = val\n\t\t}\n\t\tif val > maxVal {\n\t\t\tmaxVal = val\n\t\t}\n\t}\n\n\trangeSize := maxVal - minVal + 1\n\n\t// Step 2: Count occurrences\n\tcount := make([]int, rangeSize)\n\tfor _, val := range arr {\n\t\tcount[val-minVal]++\n\t}\n\n\t// Step 3: Compute prefix sums\n\tfor i := 1; i < rangeSize; i++ {\n\t\tcount[i] += count[i-1]\n\t}\n\n\t// Step 4: Build output (right to left for stability)\n\toutput := make([]int, len(arr))\n\tfor i := len(arr) - 1; i >= 0; i-- {\n\t\tidx := count[arr[i]-minVal] - 1\n\t\toutput[idx] = arr[i]\n\t\tcount[arr[i]-minVal]--\n\t}\n\n\t// Step 5: Copy back\n\tcopy(arr, output)\n\treturn arr\n}\n```\n\n```csharp\npublic class CountingSort\n{\n public static void Sort(int[] arr)\n {\n if (arr == null || arr.Length <= 1) return;\n\n // Step 1: Find the range\n int min = arr[0], max = arr[0];\n foreach (int val in arr)\n {\n if (val < min) min = val;\n if (val > max) max = val;\n }\n\n int range = max - min + 1;\n\n // Step 2: Count occurrences\n int[] count = new int[range];\n foreach (int val in arr)\n {\n count[val - min]++;\n }\n\n // Step 3: Compute prefix sums\n for (int i = 1; i < range; i++)\n {\n count[i] += count[i - 1];\n }\n\n // Step 4: Build output (right to left for stability)\n int[] output = new int[arr.Length];\n for (int i = arr.Length - 1; i >= 0; i--)\n {\n int idx = count[arr[i] - min] - 1;\n output[idx] = arr[i];\n count[arr[i] - min]--;\n }\n\n // Step 5: Copy back\n Array.Copy(output, arr, arr.Length);\n }\n}\n```\n\n```rust\npub struct CountingSort;\n\nimpl CountingSort {\n pub fn counting_sort(arr: &mut Vec) {\n if arr.len() <= 1 {\n return;\n }\n\n // Step 1: Find the range\n let mut min_val = arr[0];\n let mut max_val = arr[0];\n for &val in arr.iter() {\n if val < min_val {\n min_val = val;\n }\n if val > max_val {\n max_val = val;\n }\n }\n\n let range = (max_val - min_val + 1) as usize;\n\n // Step 2: Count occurrences\n let mut count = vec![0; range];\n for &val in arr.iter() {\n count[(val - min_val) as usize] += 1;\n }\n\n // Step 3: Compute prefix sums\n for i in 1..range {\n count[i] += count[i - 1];\n }\n\n // Step 4: Build output (right to left for stability)\n let mut output = vec![0; arr.len()];\n for i in (0..arr.len()).rev() {\n let idx = count[(arr[i] - min_val) as usize] - 1;\n output[idx] = arr[i];\n count[(arr[i] - min_val) as usize] -= 1;\n }\n\n // Step 5: Copy back\n *arr = output;\n }\n}\n```\n\n```javascript\nfunction countingSort(arr) {\n if (arr.length <= 1) return arr;\n\n // Step 1: Find the range\n let min = arr[0], max = arr[0];\n for (const val of arr) {\n if (val < min) min = val;\n if (val > max) max = val;\n }\n\n const range = max - min + 1;\n\n // Step 2: Count occurrences\n const count = new Array(range).fill(0);\n for (const val of arr) {\n count[val - min]++;\n }\n\n // Step 3: Compute prefix sums\n for (let i = 1; i < range; i++) {\n count[i] += count[i - 1];\n }\n\n // Step 4: Build output (right to left for stability)\n const output = new Array(arr.length);\n for (let i = arr.length - 1; i >= 0; i--) {\n const idx = count[arr[i] - min] - 1;\n output[idx] = arr[i];\n count[arr[i] - min]--;\n }\n\n return output;\n}\n```\n\n```typescript\nfunction countingSort(arr: number[]): number[] {\n if (arr.length <= 1) return arr;\n\n // Step 1: Find the range\n let min = arr[0], max = arr[0];\n for (const val of arr) {\n if (val < min) min = val;\n if (val > max) max = val;\n }\n\n const range: number = max - min + 1;\n\n // Step 2: Count occurrences\n const count: number[] = new Array(range).fill(0);\n for (const val of arr) {\n count[val - min]++;\n }\n\n // Step 3: Compute prefix sums\n for (let i = 1; i < range; i++) {\n count[i] += count[i - 1];\n }\n\n // Step 4: Build output (right to left for stability)\n const output: number[] = new Array(arr.length);\n for (let i = arr.length - 1; i >= 0; i--) {\n const idx: number = count[arr[i] - min] - 1;\n output[idx] = arr[i];\n count[arr[i] - min]--;\n }\n\n return output;\n}\n```\n\n\n\n\n\n---\n\n# Example Walkthrough\n\nLet us trace through the algorithm with the array `[4, 2, 2, 8, 3, 3, 1]` to see exactly how each step works.\n\n### Step 1: Find the Range\n\n\n```shell\nInput: [4, 2, 2, 8, 3, 3, 1]\nmin = 1, max = 8\nrange = 8 - 1 + 1 = 8\n```\n\n\nWe need a count array of size 8, with indices 0 through 7 representing values 1 through 8.\n\n### Step 2: Count Occurrences\n\nWe scan the input and increment the corresponding count for each value. Remember, value v maps to index `v - min = v - 1`.\n\n\n```shell\nProcessing 4: count[3]++ count = [0, 0, 0, 1, 0, 0, 0, 0]\nProcessing 2: count[1]++ count = [0, 1, 0, 1, 0, 0, 0, 0]\nProcessing 2: count[1]++ count = [0, 2, 0, 1, 0, 0, 0, 0]\nProcessing 8: count[7]++ count = [0, 2, 0, 1, 0, 0, 0, 1]\nProcessing 3: count[2]++ count = [0, 2, 1, 1, 0, 0, 0, 1]\nProcessing 3: count[2]++ count = [0, 2, 2, 1, 0, 0, 0, 1]\nProcessing 1: count[0]++ count = [1, 2, 2, 1, 0, 0, 0, 1]\n\nFinal count: [1, 2, 2, 1, 0, 0, 0, 1]\n ^ ^ ^ ^ ^ ^ ^ ^\n 1 2 3 4 5 6 7 8 (values)\n```\n\n\nReading this: value 1 appears once, value 2 appears twice, value 3 appears twice, value 4 appears once, values 5-7 do not appear, and value 8 appears once.\n\n### Step 3: Compute Prefix Sums\n\nWe transform the count array into cumulative counts by adding each element to the sum of all elements before it.\n\n\n```shell\ncount[0] = 1 cumulative = [1, -, -, -, -, -, -, -]\ncount[1] = 1 + 2 = 3 cumulative = [1, 3, -, -, -, -, -, -]\ncount[2] = 3 + 2 = 5 cumulative = [1, 3, 5, -, -, -, -, -]\ncount[3] = 5 + 1 = 6 cumulative = [1, 3, 5, 6, -, -, -, -]\ncount[4] = 6 + 0 = 6 cumulative = [1, 3, 5, 6, 6, -, -, -]\ncount[5] = 6 + 0 = 6 cumulative = [1, 3, 5, 6, 6, 6, -, -]\ncount[6] = 6 + 0 = 6 cumulative = [1, 3, 5, 6, 6, 6, 6, -]\ncount[7] = 6 + 1 = 7 cumulative = [1, 3, 5, 6, 6, 6, 6, 7]\n```\n\n\nNow `count[i]` tells us: \"the last element with value `(i + 1)` should go at position `count[i] - 1` in the output.\" For example, `count[1] = 3` means the last element with value 2 should go at index 2 (position 3, zero-indexed as 2).\n\n### Step 4: Build Output (Right to Left)\n\nWe iterate the input from right to left, placing each element and decrementing its count.\n\n\n```shell\nOutput starts as: [_, _, _, _, _, _, _]\n\ni=6: arr[6]=1, count[0]=1, place at index 0, count[0]-- = 0\n Output: [1, _, _, _, _, _, _]\n\ni=5: arr[5]=3, count[2]=5, place at index 4, count[2]-- = 4\n Output: [1, _, _, _, 3, _, _]\n\ni=4: arr[4]=3, count[2]=4, place at index 3, count[2]-- = 3\n Output: [1, _, _, 3, 3, _, _]\n\ni=3: arr[3]=8, count[7]=7, place at index 6, count[7]-- = 6\n Output: [1, _, _, 3, 3, _, 8]\n\ni=2: arr[2]=2, count[1]=3, place at index 2, count[1]-- = 2\n Output: [1, _, 2, 3, 3, _, 8]\n\ni=1: arr[1]=2, count[1]=2, place at index 1, count[1]-- = 1\n Output: [1, 2, 2, 3, 3, _, 8]\n\ni=0: arr[0]=4, count[3]=6, place at index 5, count[3]-- = 5\n Output: [1, 2, 2, 3, 3, 4, 8]\n```\n\n\nThe final sorted array is `[1, 2, 2, 3, 3, 4, 8]`.\n\nNotice how the two 2s and the two 3s maintained their original relative order. The `2` at index 1 in the input ended up before the `2` at index 2, and the `3` at index 4 ended up before the `3` at index 5. That is stability in action, a direct result of the right-to-left traversal.\n\n\n```mermaid\nflowchart TD\n subgraph Input[\"Input Array\"]\n I0[\"4\"] ~~~ I1[\"2\"] ~~~ I2[\"2\"] ~~~ I3[\"8\"] ~~~ I4[\"3\"] ~~~ I5[\"3\"] ~~~ I6[\"1\"]\n end\n\n subgraph Count[\"Count Array (after prefix sum)\"]\n C0[\"1\"] ~~~ C1[\"3\"] ~~~ C2[\"5\"] ~~~ C3[\"6\"] ~~~ C4[\"6\"] ~~~ C5[\"6\"] ~~~ C6[\"6\"] ~~~ C7[\"7\"]\n end\n\n subgraph Output[\"Sorted Output\"]\n O0[\"1\"] ~~~ O1[\"2\"] ~~~ O2[\"2\"] ~~~ O3[\"3\"] ~~~ O4[\"3\"] ~~~ O5[\"4\"] ~~~ O6[\"8\"]\n end\n\n Input --> Count --> Output\n\n style I0 fill:#00ceff,stroke:#000,color:#000\n style I1 fill:#00ceff,stroke:#000,color:#000\n style I2 fill:#00ceff,stroke:#000,color:#000\n style I3 fill:#00ceff,stroke:#000,color:#000\n style I4 fill:#00ceff,stroke:#000,color:#000\n style I5 fill:#00ceff,stroke:#000,color:#000\n style I6 fill:#00ceff,stroke:#000,color:#000\n style C0 fill:#ffa94d,stroke:#000,color:#000\n style C1 fill:#ffa94d,stroke:#000,color:#000\n style C2 fill:#ffa94d,stroke:#000,color:#000\n style C3 fill:#ffa94d,stroke:#000,color:#000\n style C4 fill:#ffa94d,stroke:#000,color:#000\n style C5 fill:#ffa94d,stroke:#000,color:#000\n style C6 fill:#ffa94d,stroke:#000,color:#000\n style C7 fill:#ffa94d,stroke:#000,color:#000\n style O0 fill:#69db7c,stroke:#000,color:#000\n style O1 fill:#69db7c,stroke:#000,color:#000\n style O2 fill:#69db7c,stroke:#000,color:#000\n style O3 fill:#69db7c,stroke:#000,color:#000\n style O4 fill:#69db7c,stroke:#000,color:#000\n style O5 fill:#69db7c,stroke:#000,color:#000\n style O6 fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# Complexity Analysis\n\n\n| Metric | Value | Explanation |\n|--------|-------|-------------|\n| **Time Complexity** | O(n + k) | Finding min/max is O(n), counting is O(n), prefix sum is O(k), placement is O(n) |\n| **Space Complexity** | O(n + k) | Count array uses O(k) space, output array uses O(n) space |\n| **Stable** | Yes | Right-to-left placement preserves relative order of equal elements |\n| **In-place** | No | Requires O(n + k) extra space |\n| **Comparison-based** | No | Never compares two input elements |\n| **Adaptive** | No | Does the same work regardless of input order |\n\n\nHere, **n** is the number of elements in the input and **k** is the range of values (max - min + 1).\n\nThe time complexity breaks down as follows:\n\n- **Finding min and max**: One pass through the array, O(n)\n- **Counting occurrences**: One pass through the array, O(n)\n- **Computing prefix sums**: One pass through the count array, O(k)\n- **Building output**: One pass through the array, O(n)\n- **Total**: O(n + n + k + n) = O(n + k)\n\nWhen k is O(n) or smaller (for example, sorting exam scores from 0 to 100 for 10,000 students), the algorithm runs in O(n) time. When k is much larger than n (say, sorting 10 integers that range from 0 to 10 million), the O(k) term dominates and Counting Sort becomes impractical.\n\n### Comparison with Other Sorting Algorithms\n\n\n| Algorithm | Time (Average) | Time (Worst) | Space | Stable | Comparison-based |\n|-----------|---------------|--------------|-------|--------|------------------|\n| Counting Sort | O(n + k) | O(n + k) | O(n + k) | Yes | No |\n| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes | Yes |\n| Quick Sort | O(n log n) | O(n^2) | O(log n) | No | Yes |\n| Heap Sort | O(n log n) | O(n log n) | O(1) | No | Yes |\n| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(n + k) | Yes | No |\n\n\nCounting Sort wins on raw speed when k is small, but it pays for that speed with extra memory and a strict constraint on input type.\n\n---\n\n# When to Use Counting Sort\n\n### Good Use Cases\n\n- **Sorting grades or scores**: Exam scores range from 0 to 100. With k = 101 and potentially thousands of students, Counting Sort runs in O(n) and is much faster than comparison sorts.\n- **Sorting ages**: Human ages range from 0 to roughly 150. Sorting a database of millions of records by age is a perfect fit.\n- **Sorting characters**: ASCII characters have values 0-127, giving k = 128. Sorting characters in a string is a classic application.\n- **As a subroutine for Radix Sort**: Radix Sort processes one digit at a time, and each digit has a small range (0-9 for decimal). Counting Sort handles each digit pass efficiently and, critically, provides the stability that Radix Sort requires.\n- **Sorting with known, bounded keys**: Any scenario where input values come from a small, known universe.\n\n### When Not to Use\n\n- **Large range of values**: If you are sorting 1,000 integers that range from 0 to 10,000,000, the count array alone uses 10 million entries. The O(k) space and time make this far worse than O(n log n) comparison sorts.\n- **Floating-point numbers**: Counting Sort needs integer indices. You cannot directly use a float like 3.14 as an array index. (You could multiply and round, but this introduces precision issues.)\n- **Strings or complex objects without integer keys**: Counting Sort operates on integer keys. If your data does not naturally map to a small integer range, it is the wrong tool.\n- **When stability is not needed and space is limited**: If you do not care about stability and want O(1) extra space, Heap Sort or in-place Quick Sort are better choices.\n\n### The Decision Rule\n\nA practical rule of thumb: use Counting Sort when k (the range of values) is at most O(n). If k is significantly larger than n, comparison-based sorts like Merge Sort or Quick Sort will outperform it in both time and space.","pageType":"dsa"}

Counting Sort

Ashish Pratap Singh

Get Premium