# Bucket sort algorithm in JavaScript

I was asked to implement bucket sort recently from my friend.

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem. Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.

How do we sort the numbers efficiently? I would like to ask for feedback for my solution. I also performed some diagram and benchmark it against quicksort. I appreciate any feedback.

function bucketsort(arr, range_min, range_max) {
if (arr.length <= 1) {
return arr;
}
if (arr.length < 20) {
return arr.sort();
}

let result = [];
let numberOfBuckets = Math.ceil(Math.sqrt(arr.length));

for (let i = 0; i < numberOfBuckets; i++) {
result.push([]);
}

let bucketRange = (range_max - range_min) / numberOfBuckets;

for (let i = 0; i < arr.length; i++) {

let bucketIndex = Math.floor((arr[i] - range_min) / bucketRange);

result[bucketIndex].push(arr[i]);
}

let finalResult = []
for (let i = 0; i < result.length; i++) {
finalResult = finalResult.concat(bucketsort(result[i], i * bucketRange + range_min, (i+1) * bucketRange + range_min));
}

return finalResult;
}

// console.log(bucketsort([0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434, 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434], 0.0, 1.0));

// console.log(bucketsort([1,2,3,4,5,6,7,8,9,10,11,12,13,14], 0, 15));

// bucketRange = 0.33333
//
//     0.0        0.333       0.666       1.0
//     [ [       ],  [       ],  [       ]]

// calling bucketsort on large arrays compared to quicksort

let test = [];

for (let i = 0; i < 100000; i++) {
test.push(Math.random());
}

function quicksort(arr) {
return arr.sort((a, b) => {
return a - b;
});
}

console.time("quicksort: ");
quicksort(test);
console.timeEnd("quicksort: ");

console.time("bucketsort: ");
bucketsort(test, 0.0, 1.0);
console.timeEnd("bucketsort: ");

Array.sort

• What is the useless Array.sort doing at the end? – 200_success Feb 6 '19 at 18:49
• just for testing the output is the same – NinjaG Feb 6 '19 at 20:47