Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• O(d * (n + k))
  • di mana n adalah jumlah elemen, k adalah basis (10), dan d adalah jumlah digit pada nilai terbesar. Setiap dari d lintasan melakukan O(n + k) pekerjaan.
• Ketika d kecil dan tetap, kompleksitasnya seperti O(n), lebih cepat daripada O(n log n) pada pengurutan perbandingan.

Kompleksitas Ruang:

• O(n + k)
  • Setiap lintasan membuat array output berukuran n dan array hitungan berukuran k.

Ringkasan:

• Radix Sort adalah pengurutan stabil yang tidak menggunakan perbandingan dan dapat mengungguli O(n log n) untuk kunci bilangan bulat dengan jumlah digit terbatas.
• Pengurutan ini memerlukan kunci yang dapat dipecah menjadi digit dan memori tambahan, serta versi ini mengasumsikan bilangan bulat non-negatif.