ts-ds / countingSort

Function: countingSort()

function countingSort(array): void;

Defined in: sort/counting/counting.ts:31

Sorts an array of integers in place using counting sort (CLRS, chapter 8.2).

Not a comparison sort, so it is not bound by the Ω(n log n) lower bound. With k = max - min + 1:

1. count[v] — how many times each value v occurs;
2. prefix sums turn counts into positions: count[v] — how many values are <= v;
3. walking the input from the end, every value is placed at --count[v], which keeps equal values in their original order (the sort is stable).

Efficient when k is not much larger than n.

Time: best	Time: average	Time: worst	Memory	Stable	In place
O(n + k)	O(n + k)	O(n + k)	O(n + k)	yes	no¹

¹ The result is written back into array, but O(n + k) extra memory is used.

Parameters

Parameter	Type	Description
array	number[]	Integers to sort, negative values are allowed. It is modified.

Returns

void

Nothing — array itself is sorted in ascending order.

Throws

If a value is not an integer.

Throws

If max - min + 1 exceeds COUNTING_SORT_MAX_RANGE.