Time and Space Complexity

Time Complexity:

• O(n + k)
  • where n is the number of elements and k is the value range (max + 1). One pass to count, one pass over the counts to rebuild.
• When k is small and fixed, this is effectively O(n), faster than the O(n log n) of comparison sorts.

Space Complexity:

• O(n + k)
  • The count array uses O(k) and the output uses O(n).

Summary:

• Counting Sort is a stable, non-comparison sort that runs in linear time for small integer ranges.
• It is a poor fit when the value range k is very large, because the count array would be huge. This version assumes non-negative integers.