Counting Sort mengurutkan dengan menghitung kemunculan setiap nilai. Bukan comparison-based sort — bisa lebih cepat dari O(n log n)!

Kompleksitas: O(n + k) di mana k = range nilai

Syarat: Hanya untuk bilangan bulat non-negatif dengan range terbatas.

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

  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);

  // Hitung kemunculan
  for (const num of arr) {
    count[num]++;
  }

  // Rebuild array
  const result = [];
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      result.push(i);
      count[i]--;
    }
  }

  return result;
}

countingSort([4, 2, 2, 8, 3, 3, 1]);
// Count: [0, 1, 2, 2, 1, 0, 0, 0, 1]
//         0  1  2  3  4  5  6  7  8
// Result: [1, 2, 2, 3, 3, 4, 8]

Kelebihan:

• O(n) jika range kecil — lebih cepat dari comparison sort
• Stabil (dengan variasi yang mempertahankan urutan)

Kekurangan:

• Hanya untuk integer
• Boros memori jika range besar (misal [1, 1000000])
• Tidak cocok untuk floating point atau string

Kapan pakai?

• Sorting nilai ujian (0-100) → range kecil, perfect!
• Sorting usia (0-150) → bagus
• Sorting harga (0-999999) → kurang efisien, pakai Quick Sort

🎭 Analogi sehari-hari: Sorting kartu remi standar (52 kartu, value 1-13). Bukannya bandingin satu-satu, langsung counting: berapa kartu nilai 1, berapa nilai 2, dst. Lalu output: 1 sebanyak count[1], 2 sebanyak count[2], dst. Selesai. Tidak ada compare antar elemen — itulah non-comparison sort.

💡 Mengapa bisa lebih cepat dari O(n log n)? Comparison sort minimal O(n log n) secara teoretis (proven). Counting Sort bypass batas itu karena gak compare — cuma count. Tapi syarat: range integer terbatas. Kalau range besar (misal 1-trilyun), Counting Sort jadi O(trilyun) = ngalahin O(n log n).

⚠️ Jebakan umum:

• Range besar = boros memori. Sort [1, 1000000] butuh array size 1jt
• Bilangan negatif = harus shift dulu (offset). Atau pakai 2 array (negatif & positif)
• Floating point = tidak bisa langsung. Konversi ke integer atau pakai Bucket Sort
• String/object = nope, butuh compare

🎯 Counting Sort cocok untuk:

• Range kecil + integer (nilai ujian, usia, level)
• Foundation Radix Sort (sorting angka digit-by-digit)
• Kompetisi programming dengan input integer terbatas
• Bucket sort variant untuk distribusi tertentu

🧪 Tebakan cepat: Sort 10jt nilai ujian (0-100). Quick Sort: O(n log n) ≈ 230jt ops. Counting Sort: O(n + k) = O(10jt + 100) ≈ 10jt ops. 23x lebih cepat karena range kecil.

TL;DR: Counting Sort = count occurrence + rebuild. O(n+k) bisa lebih cepat dari O(n log n) untuk range integer kecil. Bypass batas comparison sort. Cocok untuk integer terbatas, bukan general-purpose.