Counting Sort

Published Jan 10, 2024
Contribute to Docs

Counting sort is an out-of-place, non-comparison sorting algorithm that sorts a list with duplicate values efficiently. It is a helpful algorithm for sorting arrays of small, non-negative integers, where it analyzes elements’ frequency distribution and places them in their final sorted positions.


  1. Find the maximum value:
  • Iterate through the input array data to find the largest element max.
    • This determines the range of values needed to be counted.
  1. Create the count array:
  • Initialize a new array count with a max + 1 size to hold each value’s frequency.
    • The size is max + 1 so that the max element is accounted for.
  • Set all elements in count to 0 initially.
  1. Count the occurrences:
  • Loop through the data array again.
  • For each element data[i], increment the corresponding count in the count array (count[data[i]]++).
    • This is to document the frequency distribution of elements in data.
  1. Create the start array:
  • Initialize a new array start of the same size as count.
  • Set start[0] to 0.
  • Based on the frequency distribution found in count, the starting indexes can be determined and stored in the start array (start[j] = start[j-1] + count[j-1] for j=1 to max).
  1. Place elements in sorted order:
  • Iterate through the data array again.
  • For each element data[a]:
    • Retrieve its corresponding position to the temp variable from the start array (temp = start[data[a]]).
    • Place the element in the result array at that position (result[temp] = data[a]).
    • Increment the start value for the next element with the same value (start[data[a]]++).
  1. Return the sorted array:
  • The result array now contains the elements of the original data array in sorted order.
  • Return the result array.


The following example written in Java shows an implementation of counting sort:

import java.util.Random;
import java.util.Arrays;
public class CountingSorting {
public static void main(String[] args) {
Random rand = new Random();
int[] arr1 = new int[10];
for(int i =0; i < arr1.length; i++){
arr1[i] = rand.nextInt(5);
System.out.println("Array Before Sort: " + Arrays.toString(arr1));
System.out.println("Array After Sort: " + Arrays.toString(countingSort(arr1)));
public static int[] countingSort(int[] data){
int[] count,start,result;
result = new int[data.length];
//Step #1
int max = Integer.MIN_VALUE;
for(int item:data)
max = Math.max(max,item);
//Step #2
count = new int[max+1];
//Step #3
for(int i = 0; i < data.length; i++){
//Step #4
start = new int[max+1];
start[0]= 0;
for(int j =1; j < start.length; j++){
start[j] = start[j-1] + count[j-1];
//Step #5
for(int a = 0; a < result.length;a++){
int temp = start[data[a]];
result[temp] = data[a];
//Step #6
return result;

The output for the above code is:

Array Before Sort: [3, 2, 1, 4, 2, 4, 2, 1, 4, 2]
Array After Sort: [1, 1, 2, 2, 2, 2, 3, 4, 4, 4]

Time Complexity

  • The first and third loops run in O(k) time, where k is max.
  • The second and last loops run in O(n) time.
  • Therefore, the total running time is O(n+k).
  • If k = O(n), then the total time is O(n).

All contributors

Looking to contribute?

Learn More on Codecademy