{"title":"Counting Sort","description":"","content":"Counting Sort runs in linear O(n + k) time, where n is the number of elements and k is the range of input values. It performs well when the range is not much larger than the number of elements, and it applies only to integer keys within a bounded range.\n\n\n\n\n\nThis chapter covers how Counting Sort works, how to implement it, and when it outperforms 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\nThe algorithm runs in three stages. First, build 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, where each index gives the position of the last element with that value. 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\nCounting replaces comparing. Instead of determining relative order by comparing pairs of elements, the algorithm determines 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, at least log2(n!) comparisons are needed 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\nThe algorithm has five steps. Each is explained below, followed by a flowchart that ties them together.\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. When the elements are all non-negative with a known maximum, the scan can be skipped and the known range used directly.\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]` gives the number of 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]` gives the number of elements with 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 return the output array directly).\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 right-to-left traversal in Step 4 is what produces stability. 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. Going right to left and decrementing the count each time places 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\n# Example Walkthrough\n\nTrace the algorithm on the array `[4, 2, 2, 8, 3, 3, 1]`, stepping through each phase.\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\nA count array of size 8 is needed, with indices 0 through 7 representing values 1 through 8.\n\n### Step 2: Count Occurrences\n\nScan the input and increment the corresponding count for each value. 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\nTransform 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]` indicates that the last element with value `(i + 1)` belongs at position `count[i] - 1` in the output. For example, `count[1] = 3` means the last element with value 2 belongs at index 2 (position 3, zero-indexed as 2).\n\n### Step 4: Build Output (Right to Left)\n\nIterate 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\nThe two 2s and the two 3s kept 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. The right-to-left traversal is what produces this stability.\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### Stability\n\nCounting sort is stable, and stability is what makes it usable as the inner pass of radix sort. The right-to-left traversal in Step 4 is the mechanism: the rightmost duplicate is placed at the highest valid position, and each earlier duplicate goes just before it. Equal elements end up in the output in the same order they appeared in the input.\n\nA left-to-right traversal would still sort correctly but would reverse the relative order of equal elements, which would break radix sort when counting sort is used as its subroutine.\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 runs faster than comparison sorts when k is small, but it trades that speed for 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 fits well.\n- **Sorting characters**: ASCII characters have values 0-127, giving k = 128. Sorting characters in a string is a common 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 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**: Sorting 1,000 integers that range from 0 to 10,000,000 needs a count array with 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. A float like 3.14 cannot serve as an array index directly. (Multiplying and rounding works but introduces precision issues.)\n- **Strings or complex objects without integer keys**: Counting Sort operates on integer keys. Data that does not naturally map to a small integer range needs a different algorithm.\n- **When stability is not needed and space is limited**: For O(1) extra space without a stability requirement, Heap Sort or in-place Quick Sort fit better.\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.\n\n---\n\n# Quiz","pageType":"dsa"}

Counting Sort

Get Premium