Counting Sort

1function countingSort(arr) {
2  const n = arr.length;
3  const max = Math.max(...arr);
4 
5  // Create count array of size max + 1
6  const count = new Array(max + 1).fill(0);
7 
8  // Count occurrences of each value
9  for (let i = 0; i < n; i++) {
10    count[arr[i]]++;
11  }
12 
13  // Build cumulative counts
14  for (let i = 1; i <= max; i++) {
15    count[i] += count[i - 1];
16  }
17 
18  // Build output array (iterate backwards for stability)
19  const output = new Array(n);
20  for (let i = n - 1; i >= 0; i--) {
21    output[count[arr[i]] - 1] = arr[i];
22    count[arr[i]]--;
23  }
24 
25  // Copy output back to arr
26  for (let i = 0; i < n; i++) {
27    arr[i] = output[i];
28  }
29 
30  return arr;
31}