## DEV Community is a community of 893,678 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Dumb Down Demistifying Dev

Posted on • Updated on

# Counting Sort

What do we understand about Counting Sort?

• One of the most effecient sorting algorithm
• Has at least 3 loops to be implemented
• Should be implemented mathematically
• Is NOT a comparison sort
• ONLY Interger values from negative to positive
• Stable algorithm
• Returns a new Array
• Time complexity
• Best is O(n+k)
• Average is O(n+k)
• Worst is O(n+k)
• Space complexity
• O(k)
``````function CountingSort(arr) {
let max = arr;
let min = arr;
arr.forEach(val => {
if (val > max) max = val;
if (val < min) min = val;
});

//! to account for negative numbers, we use max and min.
//! e.g. 10 - (-4) = 14 Array size.
//! we need a +1 position to the right for counting of left & right values
let counter_size = max - min + 1;
let counter = new Array(counter_size).fill(0);
//! the index of counter Array indicates the value of the number in arr Array
//! count the number of times the number repeats and store in index of counter Array
arr.forEach((_, i) => counter[arr[i] - min]++);

//! to get the starting position of the number from arr Array,
//! count the previous value with current value of counter Array
for (let i = 1; i < counter.length; i++) {
counter[i] += counter[i - 1];
}

let results = new Array(arr.length);
//! skip the last element as it is not used in the result
for (let i = results.length - 1; i >= 0; i--) {
//! decrement the counter before assigning value to results Array of the index position
//! assign results Array with original Array value at position i
results[--counter[arr[i] - min]] = arr[i];
}

return results;
}
``````