flowchart LR
    A["Input: [4, 2, 2, 8, 3, 3, 1]"] --> B["Count frequencies"]
    B --> C["Counts array:<br/>Idx: 0 1 2 3 4 5 6 7 8<br/>Cnt: 0 1 2 2 1 0 0 0 1"]
    C --> D["Prefix sum → positions"]
    D --> E["Output array<br/>(place each element<br/>at its position)"]
    E --> F["✅ Sorted: [1, 2, 2, 3, 3, 4, 8]"]

    style A fill:#7c3aed,color:#fff
    style B fill:#4f46e5,color:#fff
    style D fill:#6366f1,color:#fff
    style F fill:#059669,color:#fff

function countingSort(arr) {
  if (arr.length === 0) return arr;

  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;
  const counts = new Array(range).fill(0);
  const output = new Array(arr.length);

  // Step 1: Count frequencies
  for (const num of arr) {
    counts[num - min]++;
  }

  // Step 2: Prefix sum (cumulative counts)
  for (let i = 1; i < range; i++) {
    counts[i] += counts[i - 1];
  }

  // Step 3: Build output (stable: traverse input backwards)
  for (let i = arr.length - 1; i >= 0; i--) {
    const val = arr[i];
    const idx = counts[val - min] - 1;
    output[idx] = val;
    counts[val - min]--;
  }

  return output;
}

// Input:  [4, 2, 2, 8, 3, 3, 1]
// Output: [1, 2, 2, 3, 3, 4, 8]