Counting Sort

counting-sort.js

// https://www.youtube.com/watch?v=OKd534EWcdk

countingSort([1,4,1,2,7,5,30,8,2]);

function countingSort(arr) {
  const positions = calculatePositions(arr);
  const sortedArr = []
  for (let i = 0; i < arr.length; i++) {
    sortedArr[positions[arr[i]]] = arr[i]
    positions[arr[i]] += 1
  }
  return sortedArr
}

function calculatePositions(arr) {
  const positions = []
  for (let i = 0; i < arr.length; i++) {
    positions[arr[i]] = (positions[arr[i]] || 0) + 1
  }
  for (let i = 0; i < positions.length; i++) {
    positions[i] = (positions[i] || 0) + (positions[i-1] || 0)
  }
  positions.pop()
  positions.unshift(0)
  return positions
}