Counting Sort

What do we understand about Counting Sort?

• One of the most effecient sorting algorithm
• Has at least 3 loops to be implemented
• Should be implemented mathematically
• Is NOT a comparison sort
• ONLY Interger values from negative to positive
• Stable algorithm
• Returns a new Array
• Time complexity
  • Best is O(n+k)
  • Average is O(n+k)
  • Worst is O(n+k)
• Space complexity
  • O(k)

function CountingSort(arr) {
    let max = arr[0];
    let min = arr[0];
    arr.forEach(val => {
        if (val > max) max = val;
        if (val < min) min = val;
    });

    //! to account for negative numbers, we use max and min.
    //! e.g. 10 - (-4) = 14 Array size.
    //! we need a +1 position to the right for counting of left & right values
    let counter_size = max - min + 1;
    let counter = new Array(counter_size).fill(0);
    //! the index of counter Array indicates the value of the number in arr Array
    //! count the number of times the number repeats and store in index of counter Array
    arr.forEach((_, i) => counter[arr[i] - min]++);

    //! to get the starting position of the number from arr Array,
    //! count the previous value with current value of counter Array
    for (let i = 1; i < counter.length; i++) {
        counter[i] += counter[i - 1];
    }

    let results = new Array(arr.length);
    //! skip the last element as it is not used in the result
    for (let i = results.length - 1; i >= 0; i--) {
        //! decrement the counter before assigning value to results Array of the index position
        //! assign results Array with original Array value at position i
        results[--counter[arr[i] - min]] = arr[i];
    }

    return results;
}