Counting / Radix Sort

Counting sort and radix sort put integers in order without ever comparing two of them. Counting sort tallies how many times each value occurs, then reads the tallies back from low to high; radix sort applies that same counting pass one decimal digit at a time, starting from the least significant. Because they skip comparisons, both run in linear time on the right inputs — under the O(n log n) floor that any comparison sort is bound by. You will implement both on one object, countingRadixSort = { countingSort, radixSort }. See counting sort and radix sort for background.

Signature

countingRadixSort.countingSort(arr)  // integers (may be negative) -> new sorted array
countingRadixSort.radixSort(arr)     // non-negative integers -> new sorted array

Both return a brand-new array and leave the input untouched.

Examples

countingRadixSort.countingSort([4, 2, 7, 1]);    // [1, 2, 4, 7]
countingRadixSort.countingSort([-2, 5, -9, 0]);  // [-9, -2, 0, 5]
countingRadixSort.countingSort([3, 1, 3, 1, 3]); // [1, 1, 3, 3, 3]

countingRadixSort.radixSort([170, 45, 75, 90, 802, 24, 2, 66]);
// [2, 24, 45, 66, 75, 90, 170, 802]

countingRadixSort.radixSort([1, 1000, 10, 100]); // [1, 10, 100, 1000]
countingRadixSort.radixSort([5, -3, 1]);         // throws TypeError

Notes

• Counting sort spans the whole range — it builds one bucket for every integer from the smallest value to the largest, so its cost is O(n + range). Great for [0, 100]; ruinous for [0, 1e9].
• Counting sort handles negatives — offset every value by the minimum so the smallest maps to bucket 0.
• Radix sort is non-negative only — this version reads base-10 digits and assumes no sign, so throw a TypeError if a negative value slips in.
• Each radix pass must be stable — equal digits keep their existing order, which is what preserves the work of the earlier, lower-digit passes.
• No comparisons, no libraries — do not fall back to arr.sort(); the whole point is to sort by counting, not by comparing.