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

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

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

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

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

סיכום:

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