Motivasi

Radix Sort tidak pernah membandingkan dua angka secara langsung. Algoritma ini mengelompokkan angka berdasarkan satu digit pada satu waktu menggunakan pengurutan pembantu yang stabil, sehingga dapat melampaui batas O(n log n) yang tidak dapat dilewati oleh pengurutan berbasis perbandingan.

Mengapa mempelajari Radix Sort?

• Waktu hampir linear: algoritma ini berjalan dalam O(d * (n + k)), dengan d sebagai jumlah digit dan k sebagai basis (10 di sini). Untuk angka dengan jumlah digit yang terbatas, kompleksitasnya pada dasarnya O(n).
• Stabil: nilai yang sama mempertahankan urutan relatifnya, dan inilah yang membuat tahapan pengurutan digit demi digit dapat digabungkan dengan benar.
• Gagasan yang berbeda: algoritma ini menunjukkan bahwa pengurutan tidak harus berarti membandingkan, sebuah wawasan penting untuk bilangan bulat berukuran besar atau kunci dengan lebar tetap.

Komprominya: algoritma ini memerlukan kunci yang dapat dipecah menjadi digit (di sini, bilangan bulat nonnegatif) dan memori tambahan untuk bucket.