Counting Sort

Counting sort is a non-comparison sorting algorithm that counts occurrences of each element.

Time Complexity: O(n + k)

Space Complexity: O(k)

create count array of size k
count occurrences of each element
compute prefix sums
place elements into output array using count positions

Related Algorithms

Radix sort processes digits of numbers from least significant to most significant using a stable sorting algorithm.