Javascript Counting Sort implementation

Question

Is this a good way or the best way to implement Counting Sort in Javascript? Can't find a standard JS Counting Sort example.

function countingSort(arr){
  var helper = []; // This helper will note how many times each number appeared in the arr
                   // Since JS arrary is an object and elements are not continuously stored, helper's Space Complexity minor that n
  for(var i = 0; i<arr.length; i++){
    if(!helper[arr[i]]){
        helper[arr[i]] = 1;
    }else{
        helper[arr[i]] += 1;
    }
  }

  var newArr = []; 
  for(i in helper){
    while(helper[i]>0){
        newArr.push(parseInt(i));
        helper[i]--;
    }
  }
  return newArr; 
}

var arr = [5,4,3,2,1,0];
console.log(countingSort(arr)); // [0, 1, 2, 3, 4, 5]

Answer 1

The code is correct, with some comments:

• In general, the use of for..in on arrays is discouraged, but unless you define enumerable properties on the Array prototype (which is a bad idea anyway), your use of it is fine to me

• You could improve the part where you loop to push the same value several times. This can be done in "one" go by concatenating Array(helper[i]).fill(i) to the results.

You could also use reduce to make the function more functional programming style. In the extreme, it could look like this:

function countingSort(arr){
  return arr.reduce( (acc, v) => (acc[v] = (acc[v] || 0) + 1, acc), [] )
            .reduce( (acc, n, i) => acc.concat(Array(n).fill(i)), [] ); 
}

// Sample run:
var arr = [5,4,3,2,1,0];
console.log(countingSort(arr)); // [0, 1, 2, 3, 4, 5]