كيف يعمل ترتيب الدمج؟

Question

Accepted Answer

**Merge sort** هو ترتيب **divide-and-conquer**، **مستقر** يعمل في وقت مضمون **O(n log n)**. يقسم المصفوفة إلى نصين، يرتب كل نصف بشكل متكرر، ثم يدمج النصين المرتبين.

## الفكرة

عنصر واحد مرتب بالفعل (حالة الأساس). دمج قائمتين مرتبتين خطي، ونحن نقوم بـ log n مستويات من الدمج.

## مثال

```python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # sort left half
    right = merge_sort(arr[mid:])     # sort right half
    return merge(left, right)

def merge(a, b):
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:              # <= keeps it stable
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:]); result.extend(b[j:])
    return result

merge_sort([5, 2, 4, 1, 3])           # -> [1, 2, 3, 4, 5]
```

## التعقيد

- **الوقت:** O(n log n) في *جميع* الحالات (الأفضل، المتوسط، الأسوأ).
- **المساحة:** O(n) لمخازن المدمجة (ليست في المكان).

## متى يتم الاستخدام / الأخطاء

مثالي عندما تحتاج إلى **الاستقرار** أو O(n log n) مضمون، وللقوائم **المرتبطة** و**الترتيب الخارجي** للملفات الضخمة. الذاكرة الإضافية O(n) هي أساس عيبها الرئيسي.

## لماذا يهم

Merge sort يضمن O(n log n) بغض النظر عن الإدخال، بخلاف quicksort's O(n²) الحالة الأسوأ.

استقراره يحافظ على الترتيب النسبي للمفاتيح المتساوية، وهو يهم للفرز متعدد المفاتيح.

خطوة الدمج هي primitive قابلة لإعادة الاستخدام، والهيكل divide-and-conquer هو قالب ستعيد استخدامه في كل مكان.