1/**
2 * Radix Sort implementation for JavaScript arrays
3 * @param {Array} arr - The array of non-negative integers to sort
4 * @returns {Array} - A new sorted array
5 */
6function radixSort(arr) {
7  // Create a copy to avoid modifying the original array
8  const result = [...arr];
9  
10  // Edge case: empty array
11  if (result.length === 0) return result;
12  
13  // Find the maximum element to determine the number of digits
14  const max = Math.max(...result);
15  
16  // Do counting sort for every digit position
17  // Start from least significant digit (LSD) to most significant digit (MSD)
18  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
19    // Call counting sort for the current digit
20    countingSortByDigit(result, exp);
21  }
22  
23  return result;
24}
25
26/**
27 * Counting sort implementation that sorts based on a specific digit position
28 * @param {Array} arr - The array to sort
29 * @param {number} exp - The current digit position (1, 10, 100, ...)
30 */
31function countingSortByDigit(arr, exp) {
32  const n = arr.length;
33  const output = new Array(n).fill(0);
34  const count = new Array(10).fill(0); // Digits are 0-9
35  
36  // Count occurrences of each digit at the current position
37  for (let i = 0; i < n; i++) {
38    const digit = Math.floor(arr[i] / exp) % 10;
39    count[digit]++;
40  }
41  
42  // Change count[i] so that it contains the position of this digit in output[]
43  for (let i = 1; i < 10; i++) {
44    count[i] += count[i - 1];
45  }
46  
47  // Build the output array in a stable way (traversing from end to start)
48  for (let i = n - 1; i >= 0; i--) {
49    const digit = Math.floor(arr[i] / exp) % 10;
50    output[count[digit] - 1] = arr[i];
51    count[digit]--;
52  }
53  
54  // Copy the output array to arr
55  for (let i = 0; i < n; i++) {
56    arr[i] = output[i];
57  }
58}