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

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

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

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

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

סיכום:

• מיון מהיר מהיר מאוד בממוצע, והוא אלגוריתם מיון נפוץ בפועל.
• בחירה גרועה של ציר עלולה להוריד את הביצועים שלו ל-O(n²); אסטרטגיות טובות לבחירת ציר (כמו בחירה של איבר אקראי או של החציון) מונעות זאת.