Visualizers

Counting Sort Visualizer

Step-through animation of Counting Sort showing counts and output placement.

native (Canvas API) Client-side

Input Mode

Array Size (5-15)

Speed

Input Array

Count Array (Indices 0-9)

Output Array

Ready to visualize

Execution Log

Current Action:

Idle

Phase Details:

1. Count occurrences of elements in Input.

2. Cumulative sum of counts to find output positions.

3. Build Output array backwards for stability.

Counting Sort Algorithm

Counting Sort is a non-comparison-based sorting algorithm. It works by counting the occurrences of each unique element in the input list, and using arithmetic to calculate their final positions in the sorted output array.

How It Works

Find the maximum value in the input array. Create a count array of that size, filled with zeros.
Iterate through the input array, incrementing the count array at the index corresponding to each input value.
Perform a prefix sum (cumulative sum) on the count array. Each count value now stores the actual index range of the element in the sorted output.
Iterate backwards through the input array, place each element into the output array using the count values as indices, and decrement the count value.

Implementation

function countingSort(arr) {
  if (arr.length === 0) return arr;
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const range = max - min + 1;
  
  const count = Array(range).fill(0);
  const output = Array(arr.length).fill(0);
  
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
  }
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
  return arr;
}

def counting_sort(arr):
    if len(arr) == 0:
        return arr
    max_val = max(arr)
    min_val = min(arr)
    val_range = max_val - min_val + 1
    
    count = [0] * val_range
    output = [0] * len(arr)
    
    for x in arr:
        count[x - min_val] += 1
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1
    for i in range(len(arr)):
        arr[i] = output[i]
    return arr

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;
        int max = arr[0], min = arr[0];
        for (int val : arr) {
            if (val > max) max = val;
            if (val < min) min = val;
        }
        int range = max - min + 1;
        int[] count = new int[range];
        int[] output = new int[arr.length];

        for (int val : arr) {
            count[val - min]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

#include <vector>
#include <algorithm>

void countingSort(std::vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *std::max_element(arr.begin(), arr.end());
    int minVal = *std::min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    std::vector<int> count(range, 0);
    std::vector<int> output(arr.size());

    for (int x : arr) {
        count[x - minVal]++;
    }
    for (size_t i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }
    arr = output;
}

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.