ts-ds / radixSort
Function: radixSort()
ts
function radixSort(array): void;Defined in: sort/radix/radix.ts:27
Sorts an array of integers in place using LSD radix sort (CLRS, chapter 8.3).
Sorts by the last decimal digit, then by the one before it, and so on up to the most significant digit of the largest value. Each pass is a stable counting sort by one digit, so the order established by earlier (lower) digits is kept for equal higher digits.
Negative numbers are sorted by their absolute value separately and placed before the non-negative ones in reverse order.
With d digits in the largest absolute value and base b = 10:
| Time: best | Time: average | Time: worst | Memory | Stable | In place |
|---|---|---|---|---|---|
| O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | yes | no¹ |
¹ The result is written back into array, but O(n) 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.