Motivasi

Counting Sort tidak pernah membandingkan dua elemen. Algoritma ini menggunakan nilainya secara langsung sebagai indeks ke dalam array count, sehingga dapat berjalan dalam waktu linear.

Mengapa belajar Counting Sort?

• Waktu linear: algoritma ini berjalan dalam O(n + k), dengan n sebagai jumlah elemen dan k sebagai rentang nilai. Saat k kecil, algoritma ini lebih cepat daripada O(n log n).
• Stabil (jika dilakukan dengan cermat): menjadi dasar bagi Radix Sort, yang menggabungkan beberapa tahap counting sort.
• Gagasan yang berbeda: mengurutkan dengan menghitung nilai, bukan membandingkannya.

Komprominya: algoritma ini membutuhkan memori O(k) untuk array count, sehingga kurang cocok saat rentang nilainya sangat besar (misalnya, mengurutkan beberapa angka yang nilainya mencapai satu miliar).