מוטיבציה

מיון ספירה לעולם אינו משווה בין שני איברים. הוא משתמש בערכים שלהם ישירות כאינדקסים בתוך מערך count, וכך הוא יכול לפעול בזמן ליניארי.

למה ללמוד מיון ספירה?

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

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