Class CountingSort

CountingSort is a non-comparison based sorting algorithm that works by counting the number of objects having distinct key values, and then using arithmetic to calculate the position of each object in the output sequence.

Counting sort is particularly efficient when the range of input data (k) is not significantly greater than the number of objects to be sorted (n). Unlike comparison-based sorting algorithms, counting sort is not limited by the O(n log n) lower bound.

The time complexity is O(n + k) where n is the number of elements and k is the range of input, and the space complexity is O(k).

Note: This implementation is optimized for integer values. For non-integer types, consider using other sorting algorithms.

Example

const countingSort = new CountingSort([4, 2, 2, 8, 3, 3, 1]);
countingSort.sort(); // returns new array with [1, 2, 2, 3, 3, 4, 8]
// or
CountingSort.sort([4, 2, 2, 8, 3, 3, 1]); // returns new array with [1, 2, 2, 3, 3, 4, 8]
Copy

Example

const countingSort = new CountingSort([5, 3, 8, 6, 2, 7, 1, 4]);
countingSort.sort(); // returns new array with [1, 2, 3, 4, 5, 6, 7, 8]
Copy