Time and Space Complexity

Zaman Karmaşıklığı:

• O(d * (n + k))
  • burada n eleman sayısı, k taban (10) ve d en büyük değerdeki basamak sayısıdır. d geçişin her biri O(n + k) iş yapar.
• d küçük ve sabit olduğunda, bu durum O(n) gibi davranır ve karşılaştırmalı sıralamaların O(n log n) karmaşıklığından daha hızlıdır.

Alan Karmaşıklığı:

• O(n + k)
  • Her geçiş n boyutunda bir çıktı dizisi ve k boyutunda bir sayım dizisi oluşturur.

Özet:

• Radix Sort, sınırlı sayıda basamağa sahip tam sayı anahtarları için O(n log n) karmaşıklığını geçebilen, kararlı ve karşılaştırmalı olmayan bir sıralama algoritmasıdır.
• Basamaklara ayrılabilen anahtarlara ve biraz ekstra belleğe ihtiyaç duyar; ayrıca bu sürüm negatif olmayan tam sayıları varsayar.