Implement Radix Sort in JavaScript

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. It's particularly efficient for sorting large datasets of integers. Your task is to implement Radix Sort in JavaScript.

Problem Description

You need to create a JavaScript function radixSort(arr) that takes an array of non-negative integers arr and returns a new array containing the same integers sorted in ascending order.

Key Requirements:

• Implement the Radix Sort algorithm.
• The function should handle arrays of varying lengths.
• The input array will contain only non-negative integers.
• The function should return a new sorted array, not modify the original array in place.

Expected Behavior:

The function should correctly sort an array of non-negative integers. For example, given [170, 45, 75, 90, 802, 24, 2, 66], the output should be [2, 24, 45, 66, 75, 90, 170, 802].

Edge Cases:

• Empty array: An empty input array should result in an empty output array.
• Array with a single element: An array with one element should be returned as is.
• Array with duplicate numbers.
• Array with numbers of different lengths (e.g., single-digit, double-digit, triple-digit numbers).

Examples

Example 1:

Input: [170, 45, 75, 90, 802, 24, 2, 66]
Output: [2, 24, 45, 66, 75, 90, 170, 802]
Explanation: The array is sorted numerically in ascending order.

Example 2:

Input: [5, 1, 4, 2, 8]
Output: [1, 2, 4, 5, 8]
Explanation: A simple case with single-digit numbers.

Example 3:

Input: [100, 2, 500, 10, 5]
Output: [2, 5, 10, 100, 500]
Explanation: Demonstrates sorting numbers with varying digit counts.

Example 4:

Input: []
Output: []
Explanation: An empty input array should result in an empty output array.

Example 5:

Input: [42]
Output: [42]
Explanation: An array with a single element remains unchanged.

Constraints

• The input array arr will contain only non-negative integers.
• The maximum value of an integer in the array will not exceed 1,000,000,000.
• The length of the input array arr will be between 0 and 100,000.
• Your solution should aim for a time complexity that is generally better than O(N log N) for typical integer distributions, characteristic of Radix Sort.

Notes

• Radix sort typically works by repeatedly sorting the input numbers based on each digit, starting from the least significant digit to the most significant digit.
• You will likely need a helper function (like counting sort or a bucket sort variant) to sort the array based on individual digits.
• Consider how to handle numbers with different numbers of digits. You'll need to determine the maximum number of digits in the input array to know how many passes are required.
• When extracting digits, remember that the base of the number system (e.g., base 10 for decimal numbers) will be important.