22. فرز الدمج (Merge Sort): التطبيق وخطوة الدمج (الجزء 2)

يكمن جوهر كفاءة Merge Sort في دالة merge، التي تأخذ قائمتين فرعيتين مفرزتين وتدمجهما في قائمة واحدة مفرزة في زمن قدره O(N).

دالة الدمج (The Merge Function)

تخيل دمج مجموعتين من أوراق اللعب، كلاهما مفرز بالفعل. ما عليك سوى النظر إلى الورقة العلوية لكل مجموعة واختيار الأصغر لإضافتها إلى المجموعة النهائية.

1. استخدم مؤشرين، أحدهما لبداية القائمة الفرعية اليسرى (L) والآخر لبداية القائمة الفرعية اليمنى (R).
2. طالما أن كلتا القائمتين الفرعيتين تحتويان على عناصر، قارن بين العناصر المشار إليها.
3. انسخ العنصر الأصغر إلى المصفوفة النهائية وقدم مؤشره.
4. بمجرد استنفاد إحدى القوائم الفرعية، انسخ جميع العناصر المتبقية من القائمة الفرعية الأخرى.

تحليل الكفاءة

• التعقيد الزمني: O(N log N) لأسوأ حالة ومتوسطها وأفضلها.
  • يأتي log N من مرحلة 'التقسيم' (كم مرة نقسم القائمة إلى النصف).
  • يأتي N من مرحلة 'الدمج' (ننظر إلى كل عنصر مرة واحدة خلال كل مستوى دمج).
• التعقيد المكاني: مساحة مساعدة O(N)، حيث تتطلب مصفوفة مؤقتة لأداء عملية الدمج.