Counting Sort Program with Explanation and Code

2025-11-19 counting sort non-comparative sorting integer sorting frequency sorting algorithm programs stable sorting python counting sort c counting sort javascript counting sort php sorting program csharp counting sort data structures

Counting Sort is a fast, stable, non-comparative sorting algorithm ideal for sorting integers in a limited range. This page explains Counting Sort step-by-step and includes complete program examples in Python, C, JavaScript, PHP, and C#. Perfect for students and interview preparation.

Program Explanation

What is Counting Sort?

Counting Sort is a non-comparative sorting algorithm that works by counting the occurrences of each unique value in the input array. It is efficient for sorting integers within a known, limited range. Instead of comparing elements, it uses a frequency array to determine the correct positions of elements in the output array.

Steps to Solve

  1. Find the maximum value from the input array.
  2. Create a count array of size max+1 initialized to 0.
  3. Store the frequency of each element in the count array.
  4. Modify the count array to store cumulative counts.
  5. Build the output array using cumulative indices.
  6. Copy the sorted elements back to the original array.
  7. The array is now sorted in ascending order.

Key Points

  • Counting Sort does not use comparisons.
  • Time Complexity: O(n + k), where k = range of input.
  • Very efficient for small integer ranges.
  • Stable sorting algorithm.
  • Not suitable for large ranges of numbers.
  • Works best for integer data only.

Program Code


def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    index = 0
    for i in range(len(count)):
        while count[i] > 0:
            arr[index] = i
            index += 1
            count[i] -= 1

arr = list(map(int, input("Enter numbers: ").split()))
counting_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

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];

    for (int i = 0; i <= max; i++)
        count[i] = 0;

    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i]-- > 0)
            arr[index++] = i;
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    countingSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function countingSort(arr) {
  let max = Math.max(...arr);
  let count = new Array(max + 1).fill(0);

  for (let num of arr)
    count[num]++;

  let index = 0;
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      arr[index++] = i;
      count[i]--;
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
countingSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void CountingSort(int[] arr) {
        int max = arr[0];
        foreach (int num in arr)
            if (num > max) max = num;

        int[] count = new int[max + 1];

        foreach (int num in arr)
            count[num]++;

        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        CountingSort(arr);

        Console.Write("Sorted array: ");
        foreach (int val in arr)
            Console.Write(val + " ");
    }
}
      

<?php

function countingSort(&$arr) {
    $max = max($arr);
    $count = array_fill(0, $max + 1, 0);

    foreach ($arr as $num)
        $count[$num]++;

    $index = 0;
    for ($i = 0; $i <= $max; $i++) {
        while ($count[$i] > 0) {
            $arr[$index++] = $i;
            $count[$i]--;
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
countingSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1