const MAX_NUM = 10000;
const MAX_SIZE = 10000;
function countingSort(numbers) {
let maxNum = -Infinity;
for (const n of numbers) {
if (n <= maxNum) continue;
maxNum = n;
}
// counts each number in numbers
const counts = new Array(maxNum + 1).fill(0);
for (const n of numbers) {
counts[n] += 1;
}
// find each last index + 1 of each number
const cumulatedCountSum = new Array(maxNum + 1).fill(0);
cumulatedCountSum[0] = counts[0];
for (let i = 1; i < maxNum + 1; i++) {
cumulatedCountSum[i] = cumulatedCountSum[i - 1] + counts[i];
}
// sort
const answer = new Array(numbers.length);
for (let i = 0; i < numbers.length; i++) {
const n = numbers[i];
const countedIndex = cumulatedCountSum[n];
answer[countedIndex - 1] = n; // actual index = countedIndex - 1
cumulatedCountSum[n] -= 1;
}
return answer;
}
countingSort([5, 5, 5, 3, 3, 1, 1, 0, 0]);
