Counting sort is an algorithm that, in certain cases, allows you to sort an array in linear time. To use counting sort your array must only contain integers, and it is assumed you know the minimum and maximum values.
Implementation
Breakdown
(1) Create a new array counts
in which you will keep track of how many times an integer is present in your input array. The length of counts
will be determined by the range of the values in your input array. Each index in counts
will correspond to an integer, and each value at this particular index will tell us how many times the integer is present in our input.
(2) If all our integers are positive, we could just keep track of the count for each one at the index in counts
corresponding to its value (i.e. counts[3]
is where we save our count for an integer 3
). But for this algorithm to work with negatives, we must determine an offset
value to helps us map both negative and positive integers to an index in counts
.
(3) Populate counts
by iterating through your original array. Every time we encounter an integer, we increase its count by one.
(4) Initialize an array to hold the integers in ascending order.
(5) Loop through all the integers between your min
and max
. At each iteration, determine the count
for the current integer
. If the count
is 0
, we continue to the next one. But if the count
is greater than 0
, we push that integer to sortedIntegers
as many times as indicated by count
.
(6) Return your sorted array.
Complexity
In the worst-case scenario, the complexity of this algorithm is as follows:
- Time complexity:
O(n + k)
, wheren
is the numbers of integers in your original array andk
is the range of yourmin
andmax
values. - Space complexity:
O(n + k)
When k
is less or equal to n
, both complexities reduce to O(n)
.
Top comments (1)
Hi David, Thanks for your article. Did you test your implementation with negative and duplicate values? It's not working for the negative value. If you increase array index with an additional offset you should also increase auxiliary array size. In step one you need
const counts = new Array(max + min).fill(0);
instead ofconst counts = new Array(max - min + 1).fill(0);