# How the Counting Sort Algorithm Works

`Input array --> [2,3,0,5];Smallest Number in the array --> 0;Largest Number in the array --> 5;We create a loop that starts at the smallest Number and ends at the largest Number. This loop creates a new array with 6 elements.The newly created 'COUNT' array has 6 elements [0,0,0,0,0,0] with indexes [0,1,2,3,4,5];Then we loop over the input array and use each element from that array as an index for the newly created 'COUNT' array.1. Start the loop over the input array2. Element at index  with value 3. If the 'COUNT' array with index  exists4. Add 1 to the value at index  in the 'COUNT' arrayRepeat this pattern for the whole array...Updated Count Array:Indexes -> [0,1,2,3,4,5]Values --> [1,0,1,1,0,1]We then use the updated COUNT array to re-populate the input array in sorted order.The last loop in this implementation uses the integers from the smallest number to the larger number.We use those values in the 'COUNT' array and for each element with a value greater than 0, we add that integer to the beginning of the original array from smallest to greatest.This results in an updated array that looks like this --> [0,2,3,5];`

# Implementation

`const countingSort = (array, minimumValue, maximumValue) => {  // We declare an iterator and an array to hold the total number  // of each value found in the input array    let z = 0;  let count = [];  // Adds the exact number starting from the minimumValue   // to the maximumValue into the count array (each with   // a value of 0)  for (let i = minimumValue; i <= maximumValue; i++) {    count[i] = 0;  };  // Loop through the count array and for each element  // with an index === to the input array, we add 1   for (let i = 0; i < array.length; i++) {    count[array[i]] += 1;  };  // Loop from the minimumValue to the maximumValue,  // while the count includes an index found in between minValue   // and maxValue - 1, is greater than 0,  // we replace the value at array[with index z]   // (z starts at 0), with the element at value i  // and then iterate z forward  for (let i = minimumValue; i <= maximumValue; i++) {    while (count[i]-- > 0) {      array[z] = i;      z++;    }  }  return array;}`

Hint: Array indexes can’t be negative, how does the code below get around this problem?

`const countingSort2 = (array, minimumValue, maximumValue) => {  // Create a temp array with a length equal to max - min,   // with placeholder values of 0  const count = new Array(maximumValue - minimumValue + 1).fill(0);  // Create a variable that returns the minimumValue as   // an absolute (positive) number  const indexBalancer = Math.abs(minimumValue);    // Create an empty array for sorted numbers    const sortedArray = [];  // We loop through the input array  // For each number from the input array found in  // the count array, we increment its value by 1  // But this can't be achieved using negative numbers!  // Therefore we use the indexBalancer to increase the   // indexes of all numbers so they are > -1  // Here is an example: count[-3 + 5] --> count = 1   // (we have found 1 instance of the number -3 in the   // input array and placed it at index 2 in the count array)  for (let number of array) {    count[number + indexBalancer]++  }  // For each value in range, we get the tally for that  // value in the count array  // This loop goes from smallest to greatest  for (let i = minimumValue; i <= maximumValue; i++) {    let tally = count[i + indexBalancer];        // while the tally is > 0, push the element into the    // sortedArray and reduce the tally by 1    while(tally > 0) {      sortedArray.push(i);      tally--;    }  }  return sortedArray;};`

--

--