Counting sort algorithm with annotated source code. Sorting numeric values using an array as bucket and alphabetic values using an object as a bucket

counting_sort.js

// Assume you sorting an array within the range of 0-9
// [5,1,2,3] => [1,2,3,5]
// [2,3,5,5,2,0] => [0,2,2,3,5,5]
function countingSort(array) {
  // We can assume a range of values or we can determine the range ourselves.
  // [0, k) where k is the max value of the range.
  // k must be less than or equal to N
  // Each value in the range is a represented a key in a bucket
  var bucket = [], // We use the array's index as the key for the bucket
      index = 0;

  // First pass iterating thru the array.
  // Here we sum up the value for each key (index in this case) in the bucket.
  // i.e. [0, 2, 2] => (bucket) [1, 0, 2]
  for (var i = 0; i < array.length; i++) {
    bucket[array[i]] = (bucket[array[i]] || 0) + 1;
  }

  // Second pass iterating thru the array.
  // Go thru the bucket and decrement each value till it is 0,
  // in iteration assigned the bucket's key as we move along
  // the unsorted array.
  // The run time for this is exactly N
  for (var j = 0; j < bucket.length; j++) {
    while (bucket[j] > 0) {
      array[index++] = j;
      bucket[j] -= 1;
    }
  }

  // In summary there is two pass thru the entire array. So a total of O(2n)
  // This algorithm is used a subroutine in radix sort which does it sort
  // individually for each digit.
}

// ['a', 'v', 'c', 'b'] => ['a', 'b', 'c'', 'v']
function countingSortWithChar(array){
  var bucketOfChars = {},
      index = 0;

  for (var i = 0; i < 26; i++) {
    bucketOfChars[String.fromCharCode(i + 97)] = 0; // Only dealing with lowercase
  }

  for (var j = 0; j < array.length; j++) {
    bucketOfChars[array[j]]++;
  }

  for (var char in bucketOfChars) {
    if (bucketOfChars.hasOwnProperty(char)) {
      while (bucketOfChars[char] > 0) {
        array[index++] = char;
        bucketOfChars[char]--;
      }
    }
  }
}