Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• O(n + k)
  • dengan n sebagai jumlah elemen dan k sebagai rentang nilai (maks + 1). Satu kali lintasan untuk menghitung, satu kali lintasan pada hitungan untuk menyusun kembali.
• Jika k kecil dan tetap, kompleksitasnya efektif O(n), lebih cepat daripada O(n log n) pada algoritma pengurutan berbasis perbandingan.

Kompleksitas Ruang:

• O(n + k)
  • Array penghitung menggunakan O(k), dan output menggunakan O(n).

Ringkasan:

• Counting Sort adalah algoritma pengurutan stabil yang tidak berbasis perbandingan dan berjalan dalam waktu linear untuk rentang bilangan bulat yang kecil.
• Algoritma ini kurang cocok saat rentang nilai k sangat besar, karena array penghitung akan berukuran sangat besar. Versi ini mengasumsikan bilangan bulat nonnegatif.