دمج الفرز

فرز الدمج هو خوارزمية فرز طورها جون فون نيومان في عام 1945. وهي خوارزمية فرز فعالة ذات أغراض عامة وقائم على المقارنة تستخدم أسلوب فرق تسد لتقسيم قائمة كبيرة بكفاءة إلى قائمتين فرعيتين أصغر، قم بفرز القوائم الفرعية بشكل متكرر، ثم قم بدمج النتائج معًا مرة أخرى في قائمة واحدة مرتبة. يعد فرز الدمج مستقرًا، مما يعني أنه يحافظ على الترتيب الأصلي للعناصر المتساوية في القائمة.

خوارزمية

يعمل فرز الدمج باتباع الخطوات التالية:

1. التقسيم: قم بتقسيم القائمة غير المصنفة إلى قائمتين فرعيتين متساويتين تقريبًا في الحجم
2. القهر: قم بفرز كل قائمة فرعية بشكل متكرر
3. الدمج: قم بدمج القائمتين الفرعيتين المرتبتين مرة أخرى في قائمة واحدة مرتبة

تتضمن عملية الدمج أخذ قائمتين صغيرتين مرتبتين ودمجهما معًا لتكوين قائمة مرتبة أكبر. في كل خطوة، يتم أخذ أصغر عنصر من القائمة الفرعية ووضعه في مصفوفة النتائج. يتم بعد ذلك تكرار العملية حتى يتم دمج كافة القوائم الفرعية في نتيجة واحدة مرتبة.

أداء

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

خاتمة

يعد فرز الدمج خوارزمية فرز معروفة ومستقرة وفعالة وسهلة الفهم. إنها مناسبة لفرز مجموعة واسعة من أنواع البيانات، ويمكنها فرز قوائم كبيرة في وقت خطي. إن تعقيد المساحة المنخفضة يجعلها خيارًا مثاليًا للعديد من التطبيقات.