סיבוכיות זמן ומקום

סיבוכיות זמן:

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

סיבוכיות מקום:

• O(n + k)
  • בכל מעבר נבנה מערך פלט בגודל n ומערך ספירה בגודל k.

סיכום:

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