Counting Sort

Non-comparison linear time sorting

Counting Sort is an efficient algorithm for sorting integers within a specific range. Unlike Quick Sort or Merge Sort, it doesn't compare elements. Instead, it counts occurrences to determine each element's final position.

Phase

Ready

Input Array

Count Array (Index 0-9)

Output Array

Press "Start Sorting" to begin

How it Works

Counting sort assumes that each of the $n$ input elements is an integer in the range $0$ to $k$. When $k = O(n)$, the sort runs in $\Theta(n)$ time.

Stability

Counting sort is stable. By processing the input array from right to left in the final phase, it preserves the relative order of elements with equal keys.

Integer Sorting

Because it relies on array indices to sort, it is specifically designed for integers or items that can be mapped to a small integer range.

Complexity

Time Complexity$O(n + k)$

Space Complexity$O(n + k)$

Comparison Based?No

Stable?Yes

Implementation Snippet

Pseudocode

JavaScript

1for (let x of input) 
2  count[x]++;
3 
4for (let i = 1; i < K; i++)
5  count[i] += count[i-1];
6 
7for (let i = n-1; i >= 0; i--) {
8  res[count[input[i]]-1] = input[i];
9  count[input[i]]--;
10}

Implementations

Python Implementation

Pseudocode

Python

1def counting_sort(arr):
2    max_val = max(arr)
3    count = [0] * (max_val + 1)
4    output = [0] * len(arr)
5 
6    for x in arr:
7        count[x] += 1
8 
9    for i in range(1, len(count)):
10        count[i] += count[i-1]
11 
12    for i in range(len(arr) - 1, -1, -1):
13        output[count[arr[i]] - 1] = arr[i]
14        count[arr[i]] -= 1
15    
16    return output

JavaScript Implementation

Pseudocode

JavaScript

1function countingSort(arr, k) {
2  let count = new Array(k + 1).fill(0);
3  let output = new Array(arr.length);
4 
5  for (let x of arr) count[x]++;
6 
7  for (let i = 1; i <= k; i++) 
8    count[i] += count[i - 1];
9 
10  for (let i = arr.length - 1; i >= 0; i--) {
11    output[count[arr[i]] - 1] = arr[i];
12    count[arr[i]]--;
13  }
14 
15  return output;
16}

How it Works

Counting sort assumes that each of the $n$ input elements is an integer in the range $0$ to $k$. When $k = O(n)$, the sort runs in $\Theta(n)$ time.

Stability

Counting sort is stable. By processing the input array from right to left in the final phase, it preserves the relative order of elements with equal keys.

Integer Sorting

Because it relies on array indices to sort, it is specifically designed for integers or items that can be mapped to a small integer range.

Implementations

Python Implementation

Pseudocode

Python

1def counting_sort(arr):
2    max_val = max(arr)
3    count = [0] * (max_val + 1)
4    output = [0] * len(arr)
5 
6    for x in arr:
7        count[x] += 1
8 
9    for i in range(1, len(count)):
10        count[i] += count[i-1]
11 
12    for i in range(len(arr) - 1, -1, -1):
13        output[count[arr[i]] - 1] = arr[i]
14        count[arr[i]] -= 1
15    
16    return output

JavaScript Implementation

Pseudocode

JavaScript

1function countingSort(arr, k) {
2  let count = new Array(k + 1).fill(0);
3  let output = new Array(arr.length);
4 
5  for (let x of arr) count[x]++;
6 
7  for (let i = 1; i <= k; i++) 
8    count[i] += count[i - 1];
9 
10  for (let i = arr.length - 1; i >= 0; i--) {
11    output[count[arr[i]] - 1] = arr[i];
12    count[arr[i]]--;
13  }
14 
15  return output;
16}