Counting Sort Implementation in JavaScript

Counting sort is a non-comparison sorting algorithm that is efficient for sorting integers within a known range. It works by counting the occurrences of each distinct element in the input array and then using this count information to place the elements in their correct sorted positions. This challenge asks you to implement counting sort in JavaScript.

Problem Description

You are tasked with implementing the counting sort algorithm in JavaScript. The algorithm should take an array of non-negative integers as input and return a new array containing the sorted elements. The core of the algorithm involves creating a counting array to store the frequency of each element, then using this information to determine the position of each element in the sorted output array.

Key Requirements:

• The input array will contain only non-negative integers.
• You must determine the maximum value in the input array to define the size of the counting array.
• The output array should contain the sorted elements in ascending order.
• The original input array should not be modified.
• The algorithm should be stable (elements with the same value maintain their original order).

Expected Behavior:

The function should accept an array of non-negative integers and return a new, sorted array. If the input array is empty, it should return an empty array.

Edge Cases to Consider:

• Empty input array.
• Input array with all identical elements.
• Input array with a large range of values (consider memory usage).
• Input array with a single element.

Examples

Example 1:

Input: [4, 2, 2, 8, 3, 3, 1]
Output: [1, 2, 2, 3, 3, 4, 8]
Explanation: The counting array would be [0, 1, 2, 2, 1, 0, 0, 1] representing the counts of 0, 1, 2, 3, 4, 5, 6, 7, 8 respectively.  The output array is then constructed based on these counts, maintaining the original order of equal elements.

Example 2:

Input: [1, 4, 1, 2, 7, 5, 2]
Output: [1, 1, 2, 2, 4, 5, 7]
Explanation: The counting array would be [0, 2, 2, 0, 1, 0, 0, 1] representing the counts of 0, 1, 2, 3, 4, 5, 6, 7 respectively. The output array is constructed based on these counts, preserving the original order of the '1's and '2's.

Example 3:

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

Constraints

• The input array will contain only non-negative integers.
• The maximum value in the input array will be less than or equal to 1000.
• The length of the input array will be between 0 and 1000.
• The algorithm should have a time complexity of O(n + k), where n is the number of elements in the input array and k is the range of input values (max value + 1).

Notes

• Counting sort is most effective when the range of input values (k) is not significantly larger than the number of elements (n).
• Consider using a separate array to store the counts instead of modifying the input array directly.
• Remember to handle the edge case of an empty input array.
• Stability is a key characteristic of counting sort; ensure your implementation preserves the original order of elements with equal values.
• Think about how to efficiently construct the sorted output array from the counting array.