Counting Sort

/**
 * @file Counting Sort
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Sorts an array of non-negative integers using the counting sort algorithm.
 * This algorithm is efficient for sorting numbers within a small range.
 *
 * @param unsortedArray The array of non-negative integers to be sorted.
 * @param maxValueInArray The maximum value in the array. Used to find the range
 *   of vals.
 * @returns A new array containing the sorted elements.
 */
function countingSort(
  unsortedArray: number[],
  sortedArray: number[],
  maxValueInArray: number,
): void {
  const counts: number[] = Array.from({length: maxValueInArray + 1}, () => 0);

// Update the `count` array with positions of elements in the sorted array
  for (const element of unsortedArray) {
    counts[element]++;
  }

for (let i = 1; i <= maxValueInArray; i++) {
    counts[i] += counts[i - 1];
  }

for (let index = unsortedArray.length - 1; index >= 0; index--) {
    sortedArray[counts[unsortedArray[index]] - 1] = unsortedArray[index];
    counts[unsortedArray[index]]--;
  }
}

// Usage
(() => {
  const unsortedArray = [2, 5, 3, 0, 2, 3, 0, 3];
  const maxValueInArray = Math.max(...unsortedArray);
  const sortedArray: number[] = Array.from(
    {length: unsortedArray.length},
    () => 0,
  );

countingSort(unsortedArray, sortedArray, maxValueInArray);

console.log(sortedArray);
})();