Page 1 of 9
SQL HTML CSS Javascript Python Java C C++ PHP Scala C#
Counting Sort Algorithm
Counting sort is an external sorting algorithm that assumes all the input values are integers that lie
between the range 0 and k. Then mathematical computations on these input values to place them at
the correct position in the output array.
This algorithm makes use of a counter to count the frequency of occurrence of the numbers and
arrange them accordingly. Suppose, if a number m occurs 5 times in the input sequence, the counter
value of the number will become 5 and it is repeated 5 times in the output array.
Counting Sort Algorithm
The counting sort algorithm assumes that the input is relatively smaller so the algorithm is as follows
−
Step 1 − Maintain two arrays, one with the size of input elements without repetition to store the count
values and other with the size of the input array to store the output.
Step 2 − Initialize the count array with all zeroes and keep the output array empty.
Step 3 − Every time an element occurs in the input list, increment the corresponding counter value by
1, until it reaches the end of the input list.
Step 4 − Now, in the output array, every time a counter is greater than 0, add the element at its
respective index, i.e. if the counter of 0 is 2, 0 added at the 2nd position (i.e. 1st index) of the output
array. Then decrement the counter value by 1.
Page 2 of 9
Step 5 − Repeat Step 4 until all the counter values become 0. The list obtained is the output list.
COUNTING-SORT(A, B, k)
let C[0 k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to [Link]
C[A[j]] = C[A[j]] + 1
// C[i] now contains the number of elements equal to i.
for i = 1 to k
C[i] = C[i] + C[i 1]
// C[i] now contains the number of elements less than or equal to i.
for j = [Link] downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j 1]
Analysis
The average case time complexity for the counting sort algorithm is same as bucket sort. It runs in (n)
time.
Example
Consider an input list to be sorted, 0, 2, 1, 4, 6, 2, 1, 1, 0, 3, 7, 7, 9.
For easier computations, let us start with single digit numbers.
Step 1
Create two arrays: to store counters and the output. Initialize the counter array with zeroes.
Page 3 of 9
Step 2
After incrementing all the counter values until it reaches the end of the input list, we achieve −
Step 3
Now, push the elements at the corresponding index in the output list.
Page 4 of 9
Step 4
Decrement the counter by 1 after adding the elements in the output array. Now, 1 is added at the 4th
index.
Step 5
Add the remaining values preceding the index in previous step.
Page 5 of 9
Step 6
After adding the last values, we get −
The final sorted output is achieved as 0, 0, 1, 1, 1, 2, 2, 3, 4, 6, 7, 7, 9
Powered by:
Page 6 of 9
Implementation
The counting sort implementation works closely with the algorithm where we construct an array to
store the frequency of each element of the input array. Based on these frequencies, the elements are
placed in the output array. Repetitive elements are also sorted in the counting sort algorithm.
Example
In this chapter, we look into the counting sort program implemented in four different programming
languages.
C C++ Java Python
Open Compiler
#include<stdio.h>
int countingsort(int a[], int n){
int i, j;
int output[15], c[100];
for (i = 0; i < 100; i++)
c[i] = 0;
for (j = 0; j < n; j++)
++c[a[j]];
for (i = 1; i <= 99; i++)
c[i] += c[i-1];
for (j = n-1; j >= 0; j--) {
output[c[a[j]] - 1] = a[j];
--c[a[j]];
}
printf("\nAfter sorting array elements are: ");
for (i = 0; i<n; i++)
printf("%d ", output[i]);
}
void main(){
int n , i;
int a[] = {12, 32, 44, 8, 16};
n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are: ");
for(int i = 0; i<n; i++){
printf("%d " , a[i]);
}
Page 7 of 9
countingsort(a, n);
}
Output
Before sorting array elements are: 12 32 44 8 16
After sorting array elements are: 8 12 16 32 44
TOP TUTORIALS
Python Tutorial
Java Tutorial
C++ Tutorial
C Programming Tutorial
C# Tutorial
PHP Tutorial
R Tutorial
HTML Tutorial
CSS Tutorial
JavaScript Tutorial
SQL Tutorial
TRENDING TECHNOLOGIES
Cloud Computing Tutorial
Amazon Web Services Tutorial
Microsoft Azure Tutorial
Git Tutorial
Ethical Hacking Tutorial
Docker Tutorial
Kubernetes Tutorial
DSA Tutorial
Spring Boot Tutorial
SDLC Tutorial
Unix Tutorial
Page 8 of 9
CERTIFICATIONS
Business Analytics Certification
Java & Spring Boot Advanced Certification
Data Science Advanced Certification
Cloud Computing And DevOps
Advanced Certification In Business Analytics
Artificial Intelligence And Machine Learning
DevOps Certification
Game Development Certification
Front-End Developer Certification
AWS Certification Training
Python Programming Certification
COMPILERS & EDITORS
Online Java Compiler
Online Python Compiler
Online Go Compiler
Online C Compiler
Online C++ Compiler
Online C# Compiler
Online PHP Compiler
Online MATLAB Compiler
Online Bash Compiler
Online SQL Compiler
Online Html Editor
ABOUT US | OUR TEAM | CAREERS | JOBS | CONTACT US | TERMS OF USE |
PRIVACY POLICY | REFUND POLICY | COOKIES POLICY | FAQ'S
Page 9 of 9
Tutorials Point is a leading Ed Tech company striving to provide the best learning material on technical
and non-technical subjects.
© Copyright 2025. All Rights Reserved.