מוטיבציה

מיון Radix לעולם אינו משווה ישירות בין שני מספרים. הוא מקבץ אותם לפי ספרה אחת בכל פעם בעזרת מיון עזר יציב, וכך הוא מצליח להתגבר על מחסום O(n log n) שמיוני השוואה אינם יכולים לעבור.

למה כדאי ללמוד מיון Radix?

• זמן כמעט ליניארי: הוא פועל בזמן O(d * (n + k)), כאשר d הוא מספר הספרות ו-k הוא הבסיס (10 כאן). עבור מספרים שמספר הספרות שלהם חסום, מדובר למעשה ב-O(n).
• יציב: ערכים שווים שומרים על הסדר היחסי ביניהם, וזה בדיוק מה שמאפשר למעברים לפי ספרה להשתלב כראוי.
• רעיון שונה: הוא מראה שמיון לא חייב להתבסס על השוואות, תובנה חשובה כשעובדים עם מספרים שלמים גדולים או מפתחות ברוחב קבוע.

הפשרה: הוא דורש מפתחות שאפשר לפרק לספרות (כאן, מספרים שלמים לא שליליים) וקצת זיכרון נוסף עבור הדליים.