Implement Counting Sort in JavaScript

Counting sort is a non-comparison-based sorting algorithm that operates by counting the occurrences of each distinct element in the input array. This makes it highly efficient for sorting arrays of integers within a known, limited range. This challenge will test your understanding and implementation of this specific sorting technique.

Problem Description

Your task is to implement the countingSort function in JavaScript. This function will take an array of non-negative integers as input and return a new array containing the same elements, sorted in ascending order.

Requirements:

• The function should accept an array of non-negative integers.
• The function should return a new sorted array, leaving the original array unchanged.
• The algorithm must be Counting Sort.
• Handle potential edge cases such as empty arrays or arrays with a single element.

Expected Behavior:

Given an input array of non-negative integers, the countingSort function should produce an output array where the elements are arranged from smallest to largest.

Examples

Example 1:

Input: [4, 2, 2, 8, 3, 3, 1]
Output: [1, 2, 2, 3, 3, 4, 8]
Explanation: The counting sort algorithm will count the occurrences of each number and then reconstruct the sorted array.

Example 2:

Input: [10, 4, 5, 9, 1, 7, 3, 8, 2, 6]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Explanation: A straightforward sorting of numbers within a range.

Example 3:

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

Example 4:

Input: [5]
Output: [5]
Explanation: An array with a single element is already sorted.

Constraints

• The input array will only contain non-negative integers (integers >= 0).
• The maximum value in the input array will not exceed 1000. (This implies the range of numbers is manageable).
• The length of the input array will be between 0 and 10,000.
• The solution should aim for an efficient implementation of Counting Sort.

Notes

Counting sort works best when the range of input values is not significantly larger than the number of elements to be sorted. The core idea is to use an auxiliary array to store the counts of each distinct element. You'll need to determine the maximum value in the input array to define the size of your counting array. Remember to handle the cumulative counts to correctly place elements in the sorted output.