ترتيب الدمج

ترتيب الدمج (merge sort) خوارزمية ترتيب قائمة على استراتيجية تقسيم وتغلب، وتتألف من مرحلتي "التقسيم" و"الدمج" الموضحتين في الشكل أدناه.

1. مرحلة التقسيم: قسّم المصفوفة تعاودياً عند نقطة المنتصف، مما يختزل مسألة ترتيب مصفوفة طويلة إلى مسألة ترتيب مصفوفات أقصر.
2. مرحلة الدمج: عندما يصبح طول المصفوفة الفرعية 1، توقف عن التقسيم وابدأ الدمج، بدمج المصفوفات الفرعية المرتبة الأقصر على اليسار واليمين باستمرار في مصفوفة مرتبة أطول حتى تكتمل العملية.

سير الخوارزمية

كما يوضح الشكل أدناه، تقسم "مرحلة التقسيم" المصفوفة تعاودياً من نقطة المنتصف إلى مصفوفتين فرعيتين من الأعلى إلى الأسفل.

1. احسب منتصف المصفوفة mid، وقسّم تعاودياً المصفوفة الفرعية اليسرى (المجال [left, mid]) والمصفوفة الفرعية اليمنى (المجال [mid + 1, right]).
2. كرر الخطوة 1. تعاودياً حتى يصبح طول المصفوفة الفرعية 1.

تدمج "مرحلة الدمج" المصفوفتين الفرعيتين اليسرى واليمنى في مصفوفة مرتبة من الأسفل إلى الأعلى. لاحظ أن الدمج يبدأ من المصفوفات الفرعية ذات الطول 1، لذا فإن كل مصفوفة فرعية تشارك في هذه المرحلة مرتبة بالفعل.

يتوافق الترتيب التعاودي لترتيب الدمج مع الاجتياز اللاحق لشجرة ثنائية.

• الاجتياز اللاحق: اجتَز الشجرة الفرعية اليسرى تعاودياً أولاً، ثم اجتَز الشجرة الفرعية اليمنى تعاودياً، وأخيراً عالج العقدة الجذرية.
• ترتيب الدمج: عالج المصفوفة الفرعية اليسرى تعاودياً أولاً، ثم عالج المصفوفة الفرعية اليمنى تعاودياً، وأخيراً نفّذ الدمج.

يُعرض تنفيذ ترتيب الدمج في الشيفرة أدناه. لاحظ أن المجال المراد دمجه في nums هو [left, right]، بينما المجال المقابل في tmp هو [0, right - left].

/* ترتيب الدمج */
func mergeSort(nums []int, left, right int) {
	// شرط الإنهاء
	if left >= right {
		return
	}
	// مرحلة التقسيم والدمج
	mid := left + (right - left) / 2
	mergeSort(nums, left, mid)
	mergeSort(nums, mid+1, right)
	// مرحلة الدمج
	merge(nums, left, mid, right)
}

/* ترتيب الدمج */
function mergeSort(nums: number[], left: number, right: number): void {
    // شرط الإنهاء
    if (left >= right) return; // أنهِ التعاود عندما يصبح طول المصفوفة الفرعية 1
    // مرحلة التقسيم والدمج
    let mid = Math.floor(left + (right - left) / 2); // احسب نقطة المنتصف
    mergeSort(nums, left, mid); // عالج المصفوفة الفرعية اليسرى تعاودياً
    mergeSort(nums, mid + 1, right); // عالج المصفوفة الفرعية اليمنى تعاودياً
    // مرحلة الدمج
    merge(nums, left, mid, right);
}

خصائص الخوارزمية

• التعقيد الزمني $O(n \log n)$؛ ترتيب الدمج غير تكيّفي (non-adaptive): تنتج مرحلة التقسيم شجرة تعاود بارتفاع $\log n$، ويبلغ إجمالي عدد العمليات المنفذة أثناء الدمج في كل مستوى $n$، لذا فإن التعقيد الزمني الكلي هو $O(n \log n)$.
• التعقيد المكاني $O(n)$؛ ترتيب الدمج ليس في المكان (in-place): عمق التعاود $\log n$، وهو ما يستهلك مساحة إطارات المكدس $O(\log n)$. وتتطلب عملية الدمج مصفوفة مساعدة تستهلك مساحة إضافية $O(n)$.
• ترتيب مستقر: أثناء الدمج، يبقى الترتيب النسبي للعناصر المتساوية دون تغيير.

ترتيب القوائم المترابطة

بالنسبة إلى القوائم المترابطة، يتمتع ترتيب الدمج بمزايا كبيرة على خوارزميات الترتيب الأخرى، كما يمكنه تقليل التعقيد المكاني لمهمة الترتيب إلى $O(1)$.

• مرحلة التقسيم: يمكن استخدام التكرار بدلاً من التعاود لتقسيم القائمة المترابطة، وبذلك تُلغى مساحة إطارات المكدس التي يستهلكها التعاود.
• مرحلة الدمج: في القوائم المترابطة، لا يتطلب إدراج العقد وحذفها سوى تحديث المؤشرات، لذا لا تحتاج مرحلة الدمج (دمج قائمتين مترابطتين مرتبتين قصيرتين في قائمة مترابطة مرتبة أطول) إلى إنشاء قائمة مترابطة إضافية.

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