Time and Space Complexity

تعقيد الوقت (Time Complexity):

• أفضل الحالات، ومتوسطها، وأسوأها: O(n log n)
  • يتم تقسيم المصفوفة إلى نصفين حوالي log n من المرات، ويقوم كل مستوى بعمل O(n) للدمج. لا يعتمد وقت التشغيل على ترتيب المدخلات.

تعقيد المساحة (Space Complexity):

• O(n)
  • على عكس خوارزميات الترتيب الموضعي (in-place sorts)، يقوم فرز الدمج (Merge Sort) ببناء مصفوفات جديدة أثناء الدمج، لذا فهو يحتاج إلى ذاكرة إضافية تتناسب مع حجم المدخلات.

الملخص:

• فرز الدمج (Merge Sort) سريع ويمكن التنبؤ به: O(n log n) في كل الحالات.
• إنه مستقر (stable)، لذا تحافظ العناصر المتساوية على ترتيبها.
• المقايضة هي ذاكرة O(n) الإضافية التي يستخدمها للدمج.