# Counting Sort

Let's learn the counting sort algorithm.

## We'll cover the following

## Overview

Counting sort is a non-comparison-based sorting algorithm based on keys between a specific range, that works by sorting the elements of an array by counting the number of occurrences of each distinct element in the array.An auxiliary array is used, and the count is stored in it. Sorting is done on it by mapping the count as an index of the auxiliary array.

## Algorithm

Given an array

`arr`

, calculate the maximum value.Create an auxiliary array of the maximum value

$+1$ length and initialize it with$0$ .Calculate the frequency of each element of the given array

`arr`

and store it in the auxiliary array.Now, update the

`frequencies(count)`

of the auxiliary array so that it contains the sum of frequencies of each element in the given array`arr`

.Find the index of each element of the given array(the value of the given array will be the corresponding index at the

`sorted_array`

) in the auxiliary array and subtract the element by$1$ and place it(the value) at the corresponding index in the auxiliary array.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy