SimuVedaAlgorithms Lab Open in the lab

Sorting / Intermediate

Counting Sort Visualizer

No comparisons at all. Count how many times each value appears, then write the values back from smallest to largest.

Start the Counting Sort simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n + k)
Average timeO(n + k)
Worst timeO(n + k)
Extra spaceO(k)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Make a counter for every possible value. [5, 1, 4, 2, 8]
  2. Read 5. Its count is now 1.
  3. Read 1. Its count is now 1.
  4. Read 4. Its count is now 1.
  5. Read 2. Its count is now 1.
  6. Read 8. Its count is now 1.
  7. Now write the values back, smallest first.
  8. Write 1 at index 0. [1, 5, 4, 2, 8]
  9. Write 2 at index 1. [1, 2, 5, 4, 8]
  10. Write 4 at index 2. [1, 2, 4, 5, 8]
  11. Write 5 at index 3.
  12. Write 8 at index 4.
  13. Sorted with 5 reads, 5 writes and zero comparisons.

Try it with your own input →

Counting sort in Java, Python, C++, C and JavaScript

void countingSort(int[] a, int max) {
  int[] count = new int[max + 1];
  for (int x : a) count[x]++;
  int k = 0;
  for (int v = 0; v <= max; v++) {
    while (count[v]-- > 0) a[k++] = v;
  }
}
def counting_sort(a, max_v):
    count = [0] * (max_v + 1)
    for x in a:
        count[x] += 1
    k = 0
    for v in range(max_v + 1):
        while count[v] > 0:
            a[k] = v; k += 1; count[v] -= 1
void countingSort(vector<int>& a, int maxV) {
  vector<int> count(maxV + 1, 0);
  for (int x : a) count[x]++;
  int k = 0;
  for (int v = 0; v <= maxV; v++) {
    while (count[v]-- > 0) a[k++] = v;
  }
}
#include <stdlib.h>

void countingSort(int a[], int n, int max) {
  int *count = calloc(max + 1, sizeof(int));
  for (int x = 0; x < n; x++) count[a[x]]++;
  int k = 0;
  for (int v = 0; v <= max; v++) {
    while (count[v]-- > 0) a[k++] = v;
  }
  free(count);
}
function countingSort(a, max) {
  const count = new Array(max + 1).fill(0);
  for (const x of a) count[x]++;
  let k = 0;
  for (let v = 0; v <= max; v++) {
    while (count[v]-- > 0) a[k++] = v;
  }
}

In an interview

It beats O(n log n) only when the value range k is small, like ages or marks. Radix sort applies it digit by digit for bigger numbers.

More sorting