Bucket Sort Implementation in JavaScript

Bucket sort is a sorting algorithm that works by distributing elements into a number of buckets. It's particularly effective when the input is uniformly distributed over a range. This challenge asks you to implement bucket sort in JavaScript, demonstrating your understanding of sorting algorithms and data structure manipulation.

Problem Description

You are tasked with creating a JavaScript function bucketSort(arr) that sorts an array of numbers using the bucket sort algorithm. The function should take an unsorted array of numbers as input and return a new sorted array. The algorithm should distribute the elements into buckets, sort each bucket individually (using insertion sort for simplicity), and then concatenate the sorted buckets to produce the final sorted array.

Key Requirements:

• Bucket Creation: Divide the input array's range into a specified number of buckets.
• Distribution: Place each element of the input array into the appropriate bucket based on its value.
• Bucket Sorting: Sort each bucket individually. For this challenge, use insertion sort within each bucket.
• Concatenation: Combine the sorted buckets into a single sorted array.
• Non-Mutating: The original input array should not be modified. The function must return a new sorted array.

Expected Behavior:

The function should correctly sort arrays of numbers, including those with duplicate values and negative numbers. It should handle edge cases gracefully (see below).

Edge Cases to Consider:

• Empty Array: The function should return an empty array if the input array is empty.
• Array with One Element: The function should return the original array if it contains only one element.
• Negative Numbers: The algorithm should correctly handle negative numbers within the input array.
• Uniform Distribution: While bucket sort performs best with uniformly distributed data, your implementation should still produce a sorted result even if the data is not uniformly distributed.

Examples

Example 1:

Input: [4, 1, 3, 0, 2]
Output: [0, 1, 2, 3, 4]
Explanation: The array is divided into 5 buckets. Each element is placed in its corresponding bucket. Each bucket is sorted using insertion sort. Finally, the buckets are concatenated to produce the sorted array.

Example 2:

Input: [-5, 2, 8, 0, -2, 1]
Output: [-5, -2, 0, 1, 2, 8]
Explanation: The array is divided into buckets that accommodate negative and positive numbers. Elements are distributed and sorted within their respective buckets, resulting in a correctly sorted array.

Example 3:

Input: []
Output: []
Explanation: An empty array is returned as there are no elements to sort.

Constraints

• The input array arr will contain only numbers (integers or floats).
• The number of buckets will be determined by the length of the input array. Specifically, use n buckets, where n is the length of the input array.
• The input array arr can contain any number of elements, including zero.
• The algorithm should have a time complexity of O(n+k) on average, where n is the number of elements and k is the number of buckets. While achieving this perfectly is difficult without assumptions about data distribution, strive for efficiency.
• The space complexity should be O(n+k).

Notes

• Insertion sort is a simple sorting algorithm suitable for small buckets. You can implement it as a helper function within bucketSort.
• Consider how to determine the appropriate bucket index for each element. A simple approach is to use the element's value divided by the range of the input array.
• Remember to create a new sorted array and return it, leaving the original array unchanged.
• Think about how to handle the case where all elements fall into the same bucket.