Bucket Sort

Bucket sort is mainly useful when input is uniformly distributed over a range.

bucketSort(arr[], n)
1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
.......a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.

The sorting part takes O(n) time on average if all numbers are uniformly distributed.

vector<float> bucketSort(vector<float> &arr) {
    // 1. create n empty buckets
    vector<list<float>> b(arr.size(), {});

    // 2. put element in different buckets
    for (auto num: arr) {
        int index = arr.size() * num;
        b[index].push_back(num);
    }

    // 3. sort individual buckets
    for (auto bucket: b) {
        bucket.sort();
    }

    // 4. concatenate all buckets
    vector<float> ans;
    for (auto bucket: b) {
        for (auto num: bucket) {
            ans.push_back(num);
        }
    }

    return ans;
}