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

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

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

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

• O(n + k)
  • מערך הספירות משתמש ב־O(k) והפלט משתמש ב־O(n).

סיכום:

• Counting Sort הוא מיון יציב שאינו מבוסס השוואות, ורץ בזמן ליניארי עבור טווחים קטנים של מספרים שלמים.
• הוא אינו מתאים כאשר טווח הערכים k גדול מאוד, מכיוון שמערך הספירות יהיה עצום. גרסה זו מניחה מספרים שלמים שאינם שליליים.