الفرز بالدمج
يقسم القائمة إلى نصفين، ويرتّب كل نصف، ثم يدمج النصفين المرتّبين في قائمة واحدة مرتّبة.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- نعم
- لا
الأفضل: كيف يزداد الوقت مع حجم القائمة n عندما تكون المدخلات هي الأسهل لهذه الخوارزمية.
المتوسط: النمو المعتاد للوقت مع n. في n² إذا تضاعف عدد القيم صار الوقت نحو أربعة أضعاف، أما n log n فينمو أبطأ بكثير.
الأسوأ: نمو الوقت مع أصعب المدخلات. مفيد عندما يجب ألا تنخفض السرعة أبدًا.
الذاكرة: كم يحتاج من ذاكرة إضافية غير القائمة. 1 يعني بضعة متغيرات، و n يعني نسخة من القائمة.
مستقر: تحافظ القيمتان المتساويتان على ترتيبهما الأصلي. يهم هذا عند الفرز حسب حقل واحد من السجل.
بلا ذاكرة إضافية: يرتّب داخل القائمة نفسها، دون قائمة ثانية.
- قيد المقارنة
- قيد النقل
- في مكانه النهائي
جرّب هذا: اختر قائمة فيها قيم مكررة كثيرة. عند تساوي قيمتين تؤخذ التي من النصف الأيسر أولًا، فتحافظ القيم المتساوية على ترتيبها.
كيف يعمل
تُقسَم القائمة مرارًا حتى تبقى في كل قطعة قيمة واحدة، وهي مرتّبة بطبيعتها. ثم تُدمج القطع أزواجًا: تُقارَن أول قيمة في كل قطعة وتؤخذ الأصغر، مرة بعد مرة. الصف المرفوع في الرسم المتحرك هو الذاكرة الإضافية المستخدمة أثناء الدمج.
متى يكون خيارًا جيدًا
عندما تحتاج سرعة تبقى جيدة حتى في أسوأ الحالات، ويجب أن تحافظ القيم المتساوية على ترتيبها. تستخدم Python وJava كلتاهما نسخة من الفرز بالدمج. عيبه الذاكرة الإضافية التي يحتاجها.