Implement Bucket Sort in JavaScript

Bucket sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. This challenge will guide you through implementing a standard bucket sort algorithm in JavaScript. Bucket sort is particularly efficient for uniformly distributed data and can achieve average-case O(n+k) time complexity, where n is the number of elements and k is the number of buckets.

Problem Description

Your task is to implement the bucket sort algorithm in JavaScript. You will be given an array of numbers and need to sort them in ascending order.

Requirements:

Function Definition: Create a JavaScript function named bucketSort that accepts one argument: arr, an array of numbers.
Bucket Creation: The algorithm should create a specified number of buckets. A common approach is to use n buckets, where n is the number of elements in the input array.
Distribution: Distribute the elements from the input array into the appropriate buckets. The bucket index for an element x can typically be calculated as floor(n * x), assuming the input numbers are between 0 (inclusive) and 1 (exclusive). For a more general case, you'll need to determine the range of your input numbers.
Bucket Sorting: Sort each individual bucket. For simplicity in this challenge, you can use JavaScript's built-in sort() method for each bucket.
Concatenation: Concatenate the sorted buckets back together to form the final sorted array.
Return Value: The function should return the sorted array.

Expected Behavior:

The function should correctly sort an array of numbers in ascending order.

Edge Cases:

Empty Array: The function should handle an empty input array gracefully, returning an empty array.
Array with Single Element: An array with one element should be returned as is.
Array with Duplicate Elements: The algorithm should correctly handle duplicate values.
Array with Negative Numbers: Consider how you will handle negative numbers. A common approach is to normalize them or adjust the bucket index calculation. For this challenge, assume input numbers are non-negative.
Array with Numbers Outside [0, 1) Range: The provided formula floor(n * x) is for numbers in the [0, 1) range. You'll need to adapt this if your input numbers can be larger or outside this range. For this challenge, we will assume positive numbers and you will need to determine the range.

Examples

Example 1:

Input: [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
Output: [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]
Explanation: The input array contains numbers between 0 and 1. We can create 6 buckets. Each number is placed into a bucket based on its value multiplied by the number of buckets. For example, 0.897 goes into bucket `floor(6 * 0.897) = floor(5.382) = 5`. After distributing, each bucket is sorted, and then concatenated.

Example 2:

Input: [10, 4, 7, 1, 5, 2, 8, 3, 6, 9]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Explanation: For an array of integers, we first find the maximum value (10 in this case). We can then use a similar distribution logic, e.g., `floor((element / max_value) * (n-1))`. Here, `n` is 10. So, 10 would go to `floor((10/10) * 9) = 9`. 1 would go to `floor((1/10) * 9) = 0`. After distribution and sorting of buckets, we get the sorted array.

Example 3:

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

Constraints

The input arr will be an array of numbers.
The numbers in the array will be non-negative.
The input array size can range from 0 to 10,000 elements.
The values of the numbers in the array can range from 0 up to 1,000,000.
The average-case time complexity should ideally be close to O(n+k), where n is the number of elements and k is the number of buckets. The worst-case complexity can be O(n^2) if all elements fall into a single bucket and a less efficient sorting algorithm is used within buckets.

Notes

To handle a general range of numbers (not just [0, 1)), you'll need to first find the minimum and maximum values in the input array. Then, you can adjust the formula for calculating the bucket index. A common formula is floor(((element - min_val) / (max_val - min_val)) * (num_buckets - 1)). Be careful with the case where max_val equals min_val.
Choosing the number of buckets is important. Using n buckets (where n is the number of elements) is a common and often effective strategy.
While JavaScript's sort() method is acceptable for sorting individual buckets in this challenge, be aware that its time complexity can vary (typically O(n log n)). For a truly optimal bucket sort, you'd ideally use a linear time sorting algorithm within the buckets if they are expected to contain a small number of elements.