Counting Sort

Counts occurrences of each value and uses arithmetic to place elements. Very fast when the range k is not much larger than n.

Best O(n+k) Avg O(n+k) Worst O(n+k) Space O(k) Stable Yes In-place No Distribution

How it works

Counts occurrences of each value and uses arithmetic to place elements. Very fast when the range k is not much larger than n.

Implementation

      
 function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (let i = 0; i < arr.length; i++) count[arr[i]]++;
  let idx = 0;
  for (let v = 0; v <= max; v++)
    while (count[v]-- > 0) arr[idx++] = v;
} def counting_sort(arr):
    mx = max(arr)
    count = [0] * (mx + 1)
    for v in arr: count[v] += 1
    idx = 0
    for v in range(mx + 1):
        while count[v] > 0:
            arr[idx] = v; idx += 1
            count[v] -= 1 void countingSort(vector<int>& arr) {
  int mx = *max_element(arr.begin(), arr.end());
  vector<int> count(mx + 1, 0);
  for (int v : arr) count[v]++;
  int idx = 0;
  for (int v = 0; v <= mx; v++)
    while (count[v]-- > 0) arr[idx++] = v;
} void CountingSort(int[] arr) {
  int max = arr.Max();
  int[] count = new int[max + 1];
  foreach (int v in arr) count[v]++;
  int idx = 0;
  for (int v = 0; v <= max; v++)
    while (count[v]-- > 0) arr[idx++] = v;
} void countingSort(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++)
    if (arr[i] > max) max = arr[i];
  int count[max + 1];
  memset(count, 0, sizeof(count));
  for (int i = 0; i < n; i++) count[arr[i]]++;
  int idx = 0;
  for (int v = 0; v <= max; v++)
    while (count[v]-- > 0) arr[idx++] = v;
} 