Problem Statement

Implement the Counting sort.   This is a way of sorting integers when the minimum and maximum value are known.

The min and max can be computed apart, or be known a priori.

Note:   we know that, given an array of integers,   its maximum and minimum values can be always found;   but if we imagine the worst case for an array that can hold up to 32 bit integers,   we see that in order to hold the counts,   an array of up to 232 elements may be needed.   I.E.:   we need to hold a count value up to 232-1,   which is a little over 4.2 Gbytes.   So the counting sort is more practical when the range is (very) limited,   and minimum and maximum values are known   a priori.     (However, as a counterexample,   the use of   sparse arrays   minimizes the impact of the memory usage,   as well as removing the need of having to know the minimum and maximum values   a priori.)

Let's start with the solution:

class CountingSort {
  public static function sort(arr:Array<Int>) {
    var min = arr[0], max = arr[0];
    for (i in 1...arr.length) {
      if (arr[i] < min)
        min = arr[i];
      else if (arr[i] > max)
        max = arr[i];
    }

    var range = max - min + 1;
    var count = new Array<Int>();
    count.resize(range * arr.length);

    for (i in 0...range) count[i] = 0;
    for (i in 0...arr.length) count[arr[i] - min]++;

    var z = 0;
    for (i in min...(max + 1)) {
      for (j in 0...count[i - min])
        arr[z++] = i;
    }
  }
}

class Main {
  static function main() {
    var integerArray = [1, 10, 2, 5, -1, 5, -19, 4, 23, 0];
    Sys.println('Unsorted Integers: ' + integerArray);
    CountingSort.sort(integerArray);
    Sys.println('Sorted Integers:   ' + integerArray);
  }
}