Bucket Sort

Sort a list of floats in [0,1) using bucket sort with insertion sort inside buckets.

sorting bucket-sort insertion-sort algorithms

Implement the function `bucket_sort(arr)` that takes a list of floats, each in the range [0, 1), and returns a new list sorted in ascending order using the bucket sort algorithm.

**Algorithm requirements:**
1. Create `n` buckets where `n = len(arr)`.
2. Each bucket is a list that collects elements using the index `int(arr[i] * n)`. Because all numbers are in [0,1), this index is between 0 and n-1.
3. Insert each element into its corresponding bucket.
4. Sort each bucket individually using insertion sort (write a helper or inline it).
5. Concatenate all buckets in order to produce the final sorted list.

The input list must not be modified. The function should return a new list.

You may assume all inputs are floats in [0, 1). The function signature is exactly: `def bucket_sort(arr):`.

Constraints

0 <= len(arr) <= 1000
Each element is a float with 0.0 <= x < 1.0
Expected time complexity: O(n + k) average where k is total cost of sorting buckets; for this problem, O(n^2) worst-case is acceptable.

Example

>>> bucket_sort([0.42, 0.32, 0.33])
[0.32, 0.33, 0.42]
>>> bucket_sort([0.1, 0.05, 0.3, 0.2])
[0.05, 0.1, 0.2, 0.3]
>>> bucket_sort([])
[]

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

The number of buckets equals the length of the input list.

Use the expression int(arr[i] * n) to determine the bucket index.

Implement insertion sort to sort each bucket before concatenating.

Handle the empty list case immediately (return []).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.