الفرز بالدمج

يقسم القائمة إلى نصفين، ويرتّب كل نصف، ثم يدمج النصفين المرتّبين في قائمة واحدة مرتّبة.

• الأفضل Ω(n log n)
• المتوسط Θ(n log n)
• الأسوأ O(n log n)
• الذاكرة O(n)
• مستقر
• يحتاج ذاكرة إضافية

ماذا تعني هذه المصطلحات؟

• الأفضل: كيف يزداد الوقت مع حجم القائمة n عندما تكون المدخلات هي الأسهل لهذه الخوارزمية.
• المتوسط: النمو المعتاد للوقت مع n. في n² إذا تضاعف عدد القيم صار الوقت نحو أربعة أضعاف، أما n log n فينمو أبطأ بكثير.
• الأسوأ: نمو الوقت مع أصعب المدخلات. مفيد عندما يجب ألا تنخفض السرعة أبدًا.
• الذاكرة: كم يحتاج من ذاكرة إضافية غير القائمة. 1 يعني بضعة متغيرات، و n يعني نسخة من القائمة.
• مستقر: تحافظ القيمتان المتساويتان على ترتيبهما الأصلي. يهم هذا عند الفرز حسب حقل واحد من السجل.
• بلا ذاكرة إضافية: يرتّب داخل القائمة نفسها، دون قائمة ثانية.