Counting Sort JavaScript, an Integer sorting algorithm

It’s running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items.

Test sorting a million integers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function counting_sort(arr, min, max) {
const count = Array(max).fill(0);
let len = arr.length;
let i = min;
let j = 0;
max++;
while (len--) count[arr[len]]++;
for (; i < max; i++) {
while (count[i]-- > 0) arr[j++] = i;
}
return arr;
}
const arr = [];
let i = 0;
for (i; i < 1000000; i++) {
arr.push(Math.floor(Math.random() * 1000000));
}
console.time('counting');
counting_sort(arr, 0, 1000000);
console.timeEnd('counting')
// counting: 46.953ms
console.time('native');
arr.sort((a, b) => a-b);
console.timeEnd('native')
// native: 388.311ms