Counting Sort

Count each element's frequency, build cumulative counts, then place elements in sorted order. Linear time when k (range) is small.

COUNTING-SORT(A, k):
  n = length(A)
  count  = array of size k+1, all zeros
  output = array of size n

  // Step 1: Count each element
  FOR i = 0 TO n-1:
    count[A[i]]++

  // Step 2: Cumulative count
  // count[i] now = number of elements <= i
  FOR i = 1 TO k:
    count[i] += count[i-1]

  // Step 3: Place elements (right-to-left for stability)
  FOR i = n-1 DOWNTO 0:
    output[count[A[i]]-1] = A[i]
    count[A[i]]--

  RETURN output