Motivation

Radix Sort hiçbir zaman iki sayıyı doğrudan karşılaştırmaz. Sayıları, karşılaştırmalı sıralamaların aşamadığı O(n log n) bariyerini aşmasını sağlayan kararlı bir yardımcı sıralama kullanarak her seferinde bir basamak olacak şekilde gruplandırır.

Neden Radix Sort öğrenilmeli?

• Doğrusalımsı zaman: d'nin basamak sayısı ve k'nın taban (burada 10) olduğu O(d * (n + k)) süresinde çalışır. Sınırlı sayıda basamağa sahip sayılar için bu, etkili bir şekilde O(n)'dir.
• Kararlı: Eşit değerler kendi aralarındaki sırayı korur; bu da basamak basamak geçişlerin doğru şekilde birleşmesini sağlayan şeydir.
• Farklı bir fikir: Sıralamanın mutlaka karşılaştırma yapmak anlamına gelmediğini gösterir; bu, büyük tam sayılar veya sabit genişlikli anahtarlar için önemli bir içgörüdür.

Dezavantajı: Basamaklara ayırabileceğiniz anahtarlara (burada negatif olmayan tam sayılar) ve kovalar için biraz fazladan belleğe ihtiyaç duyar.