/*
  Some background:
  - Most sorting algorithms like mergesort, quick sort, selection sort, run in O(n log n) time
  - Counting sort says it can do better with O(n) time but with a caveat of using more space (O(n) space)
  - Counting sort requires 2 ingredients: 
    1. The unsorted array
    2. The higest possible value in the array. So like the range
*/
const unsortedScores = [2, 5, 10, 1, 3, 7, 9];
const HIGHEST_POSSIBLE_SCORE = 10;

// O(n) time and space
function countingSort(unsortedScores, max) {
  // First we create an empty array that we are gonna populate with zeros
  // So we are going to have a 10 size array all filled with 0's
  // So countArray = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  // The index of each item in the array corresponds to the numbers in the unsortedScores array
  const countArray = [];
  for (let i=0; i<=max; i++) {
    countArray[i] = 0; 
  }
  
  // Loop through the unsortedScores array and whenever you see the number, add 1
  // countArray = [0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1]
  unsortedScores.forEach(function (i) {
     countArray[i]++;
  });
  
  // Wherever we see a value that is more than 0, we push the index of that into a new sortedArray
  
  const sortedArray = [];
  let currentIndex = 0;
  for (let num=0; num < max; num++) {
    const count = countArray[num];
    if (count > 0) {
      for (let times=0; times < count; times++) {
        sortedArray[currentIndex] = num;
      }
    }
  } 
  return sortedArray;
}