شرح خوارزمية دمج المصفوفات (Merge Sort) في بايثون خطوة بخطوة

📊 خوارزمية دمج المصفوفات (Merge Sort): سرعة وفعالية في بايثون

مرحباً بك في عالم خوارزميات الفرز المتقدمة! في هذا الدرس، سنتعلم واحدة من أهم وأكثر الخوارزميات كفاءة وانتشاراً: خوارزمية دمج المصفوفات (Merge Sort). 🧩

إذا كنت تتذكر درسنا السابق عن خوارزمية فرز الفقاعات (Bubble Sort)، فأنت تعلم أنها كانت بسيطة لكنها بطيئة مع البيانات الكبيرة. اليوم، سنتعلم خوارزمية ذكية تستخدم استراتيجية "فرّق تسد" (Divide and Conquer) لفرز البيانات بسرعة كبيرة، حتى لو كانت المصفوفة ضخمة!

🔍 ما هي خوارزمية دمج المصفوفات (Merge Sort)؟

Merge Sort هي خوارزمية فرز تعتمد على استراتيجية "فرّق تسد". الفكرة الأساسية بسيطة جداً:

1. فرّق (Divide): قسّم المصفوفة الأصلية إلى نصفين متساويين تقريباً.
2. تسّد (Conquer): رتّب (فرز) كل نصف بشكل مستقل (عادةً باستخدام نفس الخوارزمية بشكل متكرر).
3. ادمج (Combine): ادمج النصفين المرتبين للحصول على مصفوفة واحدة مرتبة بالكامل.

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

🧠 كيف تعمل خوارزمية Merge Sort؟ (خطوة بخطوة)

لنفترض أن لدينا المصفوفة التالية ونريد ترتيبها تصاعدياً: [38, 27, 43, 3, 9, 82, 10]

الخطوة الأولى: التقسيم (Divide) نقسم المصفوفة إلى نصفين متساويين قدر الإمكان.

• النصف الأيسر: [38, 27, 43, 3]
• النصف الأيمن: [9, 82, 10]

الخطوة الثانية: التقسيم والتسّد بشكل متكرر (Recursive Conquer) نواصل تقسيم كل نصف حتى نصل إلى مصفوفات صغيرة تحتوي على عنصر واحد فقط (مصفوفة من عنصر واحد تعتبر مفروزة تلقائياً).

[38, 27, 43, 3, 9, 82, 10]
        |
        | (تقسيم)
        |
[38, 27, 43, 3] | [9, 82, 10]
        |               |
        | (تقسيم)       | (تقسيم)
        |               |
[38, 27] | [43, 3] | [9, 82] | [10]
    |         |         |        |
    |(تقسيم)  |(تقسيم) |(تقسيم)| (عنصر واحد -> مفروز)
    |         |         |        |
[38] | [27] | [43] | [3] | [9] | [82] | [10]
(جميعها مصفوفات من عنصر واحد -> مفروزة)

الخطوة الثالثة: الدمج (Combine/ Merge) هنا تبدأ المرحلة الذكية. نبدأ في دمج المصفوفات الصغيرة (المفروزة) للحصول على مصفوفات أكبر مرتبة.

1. ندمج [38] و [27] للحصول على [27, 38] (نقارن 38 و 27، نأخذ الأصغر أولاً).
2. ندمج [43] و [3] للحصول على [3, 43].
3. ندمج [27, 38] و [3, 43] للحصول على [3, 27, 38, 43]. (كيف؟ سنرى في الكود!)
4. بنفس الطريقة، ندمج [9] و [82] لنحصل على [9, 82].
5. ندمج [9, 82] و [10] لنحصل على [9, 10, 82].
6. أخيراً، ندمج النصفين الكبيرين: [3, 27, 38, 43] و [9, 10, 82] لنحصل على المصفوفة النهائية المرتبة: [3, 9, 10, 27, 38, 43, 82]. 🎉

💻 تنفيذ خوارزمية Merge Sort في بايثون

الآن، لنترجم هذه الخطوات إلى كود بايثون. سنكتب دالتين:

1. دالة أساسية merge_sort مسؤولة عن التقسيم.
2. دالة مساعدة merge مسؤولة عن دمج مصفوفتين مرتبتين.

# دالة الدمج المسؤولة عن دمج مصفوفتين مرتبتين
def merge(left_list, right_list):
    """
    تأخذ هذه الدالة مصفوفتين مرتبتين (left_list و right_list)
    وتعيد مصفوفة واحدة مرتبة تحتوي على جميع عناصرهما.
    """
    result = []  # المصفوفة الناتجة بعد الدمج
    i = j = 0    # مؤشران لتتبع موقعنا في المصفوفتين الأيسر والأيمن

    # بينما لا نزال لدينا عناصر في كلا المصفوفتين
    while i < len(left_list) and j < len(right_list):
        if left_list[i] <= right_list[j]:
            # إذا كان العنصر في المصفوفة اليسرى أصغر أو مساوٍ، نضيفه
            result.append(left_list[i])
            i += 1  # نحرك المؤشر في المصفوفة اليسرى
        else:
            # وإلا، نضيف العنصر من المصفوفة اليمنى
            result.append(right_list[j])
            j += 1  # نحرك المؤشر في المصفوفة اليمنى

    # بعد انتهاء أحد المصفوفتين، نضيف كل العناصر المتبقية من المصفوفة الأخرى
    result.extend(left_list[i:])  # إضافة ما تبقى من left_list
    result.extend(right_list[j:]) # إضافة ما تبقى من right_list
    return result

# الدالة الرئيسية لفرز دمج المصفوفات
def merge_sort(arr):
    """
    تأخذ مصفوفة (arr) وتعيدها مرتبة باستخدام خوارزمية دمج المصفوفات.
    """
    # الشرط الأساسي للتوقف عن التقسيم: إذا كانت المصفوفة تحتوي على عنصر واحد أو أقل
    if len(arr) <= 1:
        return arr

    # 1. التقسيم (Divide): إيجاد منتصف المصفوفة
    mid = len(arr) // 2

    # 2. التسّد (Conquer): فرز النصفين بشكل متكرر
    left_half = merge_sort(arr[:mid])   # النصف الأيسر
    right_half = merge_sort(arr[mid:])  # النصف الأيمن

    # 3. الدمج (Combine): دمج النصفين المرتبين وإعادة النتيجة
    return merge(left_half, right_half)

# ====================
# تجربة الكود
# ====================
my_list = [38, 27, 43, 3, 9, 82, 10]
print("المصفوفة الأصلية:", my_list)

sorted_list = merge_sort(my_list)
print("المصفوفة بعد الترتيب (Merge Sort):", sorted_list)

🧪 مثال تشغيلي بسيط

لنرى كيف تعمل دالة merge بشكل عملي:

# مثال على دمج مصفوفتين مرتبتين
list_a = [3, 27, 38, 43]  # مصفوفة مرتبة
list_b = [9, 10, 82]      # مصفوفة مرتبة

merged_result = merge(list_a, list_b)
print("نتيجة دمج المصفوفتين:", merged_result)
# الناتج سيكون: [3, 9, 10, 27, 38, 43, 82]

⚖️ مميزات وعيوب Merge Sort

👍 المميزات:

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

👎 العيوب:

• تستهلك ذاكرة إضافية (Space): تحتاج إلى مصفوفة مساعدة للدمج، لذا تعقيدها المكاني هو O(n) وليس O(1) مثل بعض الخوارزميات البسيطة.
• أكثر تعقيداً في التنفيذ: مقارنةً بـ Bubble Sort أو Selection Sort.