# فصل ۰۴ — تقسیم و حل: `merge sort`

<div dir="rtl">

# فصل ۰۴ — تقسیم و حل: `merge sort`

## در این فصل چه یاد می‌گیری

فصلِ قبل دو الگوریتم داشت که در `n = 2,000` به حدودِ دو میلیون مقایسه می‌رسیدند. این فصل الگوریتمی می‌سازد که در `n = 8,000` — چهار برابرِ آن — فقط **`93,704`** مقایسه می‌خواهد، و ستونِ نسبتش به‌جای `4.00` عددِ **`2.19`** است.

ایده‌اش یک جمله است: **نصف کن، هر نصف را مرتب کن، دو نصفِ مرتب را ادغام کن.** و بعد می‌شماریم که این سرعت با چه چیزی خریده شده: **در `n = 8,000`، صد و سه هزار و هشتصد عضو کپی می‌شود** — حافظه‌ای که `insertion sort` اصلاً لازم نداشت.

![درختی که یک دستهٔ کارت را دو به دو می‌شکند و در راهِ برگشت، هر دو دستهٔ مرتب را به هم می‌بافد](/lesson-assets/t4-s04-merge-sort/prompt/01-image-split-and-merge.png)

آخر این فصل می‌توانی:

- دو دنبالهٔ مرتب را با یک بار عبور ادغام کنی
- `merge sort` را از صفر بنویسی و درستی‌اش را ثابت کنی
- **با عدد** نشان بدهی که کار در هر سطح `n` است و تعدادِ سطح‌ها `log n`
- حافظهٔ کمکی‌اش را بشماری و بگویی چرا رایگان نیست

## قبل از شروع

**از فصلِ ۱:** حالتِ پایه، گامِ بازگشتی، و عمقِ `call stack`.

**از فصلِ ۳:** شمردنِ مقایسه‌ها، و اینکه `selection sort` در `n = 2,000` عددِ `1,999,000` می‌دهد. **همان عدد معیارِ مقایسهٔ این فصل است.**

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-4-recursion-sorting-searching/session-04-merge-sort.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. ادغام: هستهٔ کلِ الگوریتم

قبل از هر `recursion`ی، این را حل کن: **دو فهرست داری که هرکدام جداگانه مرتب‌اند. یک فهرستِ مرتب از هر دو بساز.**

جوابش هیچ ربطی به مرتب‌سازی ندارد. **کوچک‌ترینِ نتیجه حتماً یکی از دو عضوِ اول است**، پس فقط کافی است هر بار کوچک‌ترِ آن دو را برداری و جلو بروی.

</div>

```python
def merge(left, right):
    """دو دنبالهٔ مرتب را با یک بار عبور، به یک دنبالهٔ مرتب می‌چسباند."""
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])                 # هر چه از یک طرف مانده، مرتب است
    out.extend(right[j:])
    return out


a = [10, 14, 29, 37]
b = [11, 13, 18, 25]
print("چپ  :", a)
print("راست:", b)
print("ادغام:", merge(a, b))
print("مقایسه‌های لازم: حداکثر", len(a) + len(b) - 1)
```

```text
چپ  : [10, 14, 29, 37]
راست: [11, 13, 18, 25]
ادغام: [10, 11, 13, 14, 18, 25, 29, 37]
مقایسه‌های لازم: حداکثر 7
```

<div dir="rtl">

**هشت عضو، حداکثر هفت مقایسه.** هر مقایسه دقیقاً یک عضو را نهایی می‌کند، و آخرین عضو اصلاً مقایسه نمی‌خواهد. **پس ادغام `O(n)` است** — یک بار عبور از هر دو فهرست، و نه بیشتر.

**تمامِ `merge sort` روی همین یک تابع سوار است.** بقیه‌اش فقط این است که از کجا دو فهرستِ مرتب بیاوریم.

## ۲. و جواب: از خودمان

</div>

```python
def merge_sort_traced(values, depth=0):
    """نصف کن، هر نصف را مرتب کن، دو نصفِ مرتب را ادغام کن."""
    pad = "  " * depth
    if len(values) <= 1:                 # حالتِ پایه: یک عضو، خودش مرتب است
        print(f"{pad}{values} <- پایه")
        return values
    mid = len(values) // 2
    print(f"{pad}{values} -> {values[:mid]} + {values[mid:]}")
    left = merge_sort_traced(values[:mid], depth + 1)
    right = merge_sort_traced(values[mid:], depth + 1)
    joined = merge(left, right)
    print(f"{pad}ادغام -> {joined}")
    return joined


print(merge_sort_traced([29, 10, 14, 37, 13, 25, 11, 18]))
```

```text
[29, 10, 14, 37, 13, 25, 11, 18] -> [29, 10, 14, 37] + [13, 25, 11, 18]
  [29, 10, 14, 37] -> [29, 10] + [14, 37]
    [29, 10] -> [29] + [10]
      [29] <- پایه
      [10] <- پایه
    ادغام -> [10, 29]
    [14, 37] -> [14] + [37]
      [14] <- پایه
      [37] <- پایه
    ادغام -> [14, 37]
  ادغام -> [10, 14, 29, 37]
  [13, 25, 11, 18] -> [13, 25] + [11, 18]
    [13, 25] -> [13] + [25]
      [13] <- پایه
      [25] <- پایه
    ادغام -> [13, 25]
    [11, 18] -> [11] + [18]
      [11] <- پایه
      [18] <- پایه
    ادغام -> [11, 18]
  ادغام -> [11, 13, 18, 25]
ادغام -> [10, 11, 13, 14, 18, 25, 29, 37]
[10, 11, 13, 14, 18, 25, 29, 37]
```

<div dir="rtl">

**اسمِ این الگو «تقسیم و حل» است و سه قدم دارد:** مسئله را به دو نیمهٔ مستقل بشکن، هر نیمه را به همان روش حل کن، و جوابِ دو نیمه را به هم بچسبان.

**تفاوتش با درختِ فصلِ ۲ حیاتی است.** آن‌جا دو شاخه کارِ مشترک داشتند و همان تکرار انفجار می‌ساخت. این‌جا **هر عضو دقیقاً در یکی از دو نیمه است** — هیچ کارِ مشترکی نیست، پس هیچ چیزی دو بار انجام نمی‌شود.

## ۳. شمردن، در دو جهت

حالا همان کد را با چهار شمارنده می‌نویسیم: مقایسه، عمق، **مقایسه در هر سطح**، و عضوِ کپی‌شده.

</div>

```python
from collections import Counter


def merge_sort(values, stats=None, depth=1):
    """مرتب‌شده، به‌همراهِ شمارشِ مقایسه، عمق، مقایسه در هر سطح و عضوِ کپی‌شده."""
    if stats is None:
        stats = {"comparisons": 0, "depth": 0, "per_level": Counter(), "copied": 0}
    stats["depth"] = max(stats["depth"], depth)
    if len(values) <= 1:
        return values, stats
    mid = len(values) // 2
    left = merge_sort(values[:mid], stats, depth + 1)[0]
    right = merge_sort(values[mid:], stats, depth + 1)[0]
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        stats["comparisons"] += 1
        stats["per_level"][depth] += 1
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    stats["copied"] += len(out)
    return out, stats


rng = random.Random(SEED)
LADDER = [1_000, 2_000, 4_000, 8_000]
shuffled = {n: rng.sample(range(10 * n), n) for n in LADDER}
result, stats = merge_sort(shuffled[1_000])
print("با sorted یکی است؟", result == sorted(shuffled[1_000]))
print("مقایسه:", stats["comparisons"], "· عمق:", stats["depth"])
```

```text
با sorted یکی است؟ True
مقایسه: 8709 · عمق: 11
```

<div dir="rtl">

**۸٬۷۰۹ مقایسه برای هزار عضو.** `selection sort` در همین `n` عددِ `499,500` می‌داد — **پنجاه‌وهفت برابر بیشتر.**

## ۴. چرا `n log n`: کار در هر سطح، و تعدادِ سطح‌ها

عددِ `8,709` را می‌شود شکافت، و شکافتنش کلِ استدلالِ این الگوریتم است.

</div>

```python
print("سطح   تعدادِ مقایسه در این سطح")
for level in sorted(stats["per_level"]):
    print(f"{level:>4}   {stats['per_level'][level]:>10,}")
print(f"جمع    {stats['comparisons']:>10,}   (n = 1,000)")
```

```text
سطح   تعدادِ مقایسه در این سطح
   1          998
   2          990
   3          996
   4          984
   5          974
   6          947
   7          870
   8          800
   9          662
  10          488
جمع         8,709   (n = 1,000)
```

<div dir="rtl">

**هر سطح حدودِ `1,000` مقایسه دارد — یعنی حدودِ `n`.** و دلیلش روشن است: در هر سطح، تکه‌ها با هم روی هم **کلِ فهرست** را می‌پوشانند، و ادغامِ هر تکه به اندازهٔ خودش کار دارد. **پس کارِ هر سطح `O(n)` است، فارغ از اینکه به چند تکه شکسته شده باشد.**

سطح‌های پایین‌تر کمی کمترند چون در تکه‌های کوچک، احتمالِ اینکه یک طرف زودتر تمام شود بیشتر است و باقیمانده بدونِ مقایسه کپی می‌شود. سطحِ ۱۱ هم اصلاً در جدول نیست، چون آن‌جا تکه‌ها تک‌عضوی‌اند و ادغامی در کار نیست.

**می‌ماند سؤالِ دوم: چند سطح؟** هر سطح طولِ تکه‌ها را نصف می‌کند، پس تعدادِ سطح‌ها همان تعدادِ دفعاتی است که `n` را می‌شود نصف کرد تا به ۱ برسد.

> 🌱 **ریشه‌اش کجاست:** «چند بار می‌شود `n` را نصف کرد تا به ۱ برسد» تعریفِ `log₂ n` است، و [ریشه ترمِ ۴ فصل ۸](/courses/risheh/lessons/term-4-functions/session-08-log) آن را به‌عنوانِ **وارونهٔ توان** می‌سازد. **نتیجه‌ای که آن‌جا ساخته می‌شود و این‌جا به‌کار می‌آید یک جمله است: `log` بی‌رحمانه کند رشد می‌کند** — با هزار برابر شدنِ `n`، فقط حدودِ ده واحد بالا می‌رود. جدولِ عمقِ پایین دقیقاً همین را نشان می‌دهد.

> 🤔 **اول حدس بزن:** ستونِ نسبتِ **مقایسه** و ستونِ نسبتِ **عمق** را جدا حدس بزن. **دو عدد بنویس**، بعد جدول را ببین.

</div>

```python
def sorted_stats(n):
    return merge_sort(shuffled[n])[1]


print("— مقایسه")
table([(n, sorted_stats(n)["comparisons"]) for n in LADDER], "مقایسه", ",d")
print("\n— عمقِ recursion")
table([(n, sorted_stats(n)["depth"]) for n in LADDER], "عمق", ",d")
```

```text
— مقایسه
         n            مقایسه     نسبت به سطر قبل
     1,000             8,709                   —
     2,000            19,415                2.23
     4,000            42,781                2.20
     8,000            93,704                2.19

— عمقِ recursion
         n               عمق     نسبت به سطر قبل
     1,000                11                   —
     2,000                12                1.09
     4,000                13                1.08
     8,000                14                1.08
```

<div dir="rtl">

**`2.19` و رو به پایین — این امضای `O(n log n)` است.** ترمِ ۱ فصلِ ۵ همین را در قاعده‌اش نوشته بود: «کمی بالای `2` و رو به کاهش، یعنی پابه‌پای `n` به‌علاوهٔ یک لایهٔ نصف‌کردن». **کمی بالای `2` است چون با دو برابر شدنِ `n`، هم کارِ هر سطح دو برابر می‌شود و هم یک سطحِ تازه اضافه می‌شود.**

و جدولِ دوم آن «یک سطحِ تازه» را با چشم نشان می‌دهد: **`11`، `12`، `13`، `14` — هر دو برابر شدنِ `n` دقیقاً یکی به عمق اضافه می‌کند.** این همان `log₂ n` است، بدونِ هیچ فرمولی.

حالا مدل را با اندازه‌گیری می‌سنجیم:

</div>

```python
import math

print(f"{'n':>8}{'مقایسه':>12}{'n × log2(n)':>16}{'نسبت':>10}")
for n in LADDER:
    got = sorted_stats(n)["comparisons"]
    model = n * math.log2(n)
    print(f"{n:>8,}{got:>12,}{model:>16,.0f}{got / model:>10.2f}")
```

```text
       n      مقایسه     n × log2(n)      نسبت
   1,000       8,709           9,966      0.87
   2,000      19,415          21,932      0.89
   4,000      42,781          47,863      0.89
   8,000      93,704         103,726      0.90
```

<div dir="rtl">

**نسبت در هر چهار سطر بینِ `0.87` و `0.90` می‌ماند و خیلی آرام بالا می‌رود.** یعنی شمارشِ واقعی **متناسب** با `n log₂ n` است، با ضریبی کمی کمتر از یک که با بزرگ شدنِ `n` آرام‌آرام به یک نزدیک می‌شود. **همین ماندنِ نسبت در یک بازهٔ باریک، تأییدِ مدل است** — اگر مرتبه `O(n²)` بود این ستون با هر دو برابر شدنِ `n` تقریباً دو برابر می‌شد و اگر `O(n)` بود در هر سطر حدودِ ده درصد پایین می‌آمد؛ این‌جا بالا می‌رود، پس نزدیک‌ترین شکل `n log n` است.

## ۵. حافظه‌ای که در جدولِ مقایسه دیده نمی‌شود

`merge` یک `list` تازه می‌سازد. این یعنی `merge sort` — برخلافِ دو الگوریتمِ فصلِ ۳ — **در جای خودِ داده کار نمی‌کند.**

</div>

```python
print("— عضوِ کپی‌شده در کلِ ادغام‌ها (حافظهٔ کمکی)")
table([(n, sorted_stats(n)["copied"]) for n in LADDER], "عضوِ کپی‌شده", ",d")
```

```text
— عضوِ کپی‌شده در کلِ ادغام‌ها (حافظهٔ کمکی)
         n      عضوِ کپی‌شده     نسبت به سطر قبل
     1,000             9,976                   —
     2,000            21,952                2.20
     4,000            47,904                2.18
     8,000           103,808                2.17
```

<div dir="rtl">

**ستونِ نسبتش هم `2.2` است — یعنی کلِ کپی‌ها هم `O(n log n)` است.** برای هزار عضو، نزدیک به ده هزار عضو کپی می‌شود: **در هر یک از ده سطح، یک بار کلِ فهرست.**

**ولی این عددِ کل است، نه عددی که در یک لحظه در حافظه داری.** در هر لحظه فقط ادغام‌های یک شاخه باز هستند، پس **بیشترین حافظهٔ هم‌زمان `O(n)` است، نه `O(n log n)`.** این تفاوت را در گزارش باید صریح نوشت، وگرنه هزینه را چند برابر بزرگ‌تر از واقع اعلام کرده‌ای.

> ✅ **چک کن:** در تابعِ `merge_sort` بخشِ ۳ — و در `merge` بخشِ ۱، تا هر دو یکی بمانند — علامتِ `<=` را به `<` تغییر بده و جدولِ مقایسهٔ بخشِ ۴ را دوباره بگیر. (جدولِ بخشِ ۴ از `merge_sort` می‌آید، که حلقهٔ ادغام را داخلِ خودش دارد؛ اگر فقط `merge` را عوض کنی هیچ اتفاقی نمی‌افتد.) **جواب همچنان با `sorted` یکی درمی‌آید و ستونِ نسبت هم عوض نمی‌شود** — چون داده‌های ما تکراری ندارند. **این تغییر بی‌خطر به‌نظر می‌رسد و نیست:** فصلِ ۸ نشان می‌دهد که همین یک نویسه، روی داده‌ای که عضوِ برابر دارد، خاصیتی را از بین می‌برد که کلِ مرتب‌سازیِ چندکلیدی روی آن سوار است.

## ۶. یک نویسه در شرطِ حلقه

</div>

```python
def merge_broken(left, right):
    """اشتباهِ کلاسیک: or به‌جای and در شرطِ حلقه."""
    out = []
    i = j = 0
    while i < len(left) or j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out


try:
    merge_broken([1, 3, 5], [2, 4, 6])
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
IndexError: list index out of range
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** `and` می‌گوید «تا وقتی **هر دو** طرف عضوی دارند»، `or` می‌گوید «تا وقتی **دستِ‌کم یکی** عضوی دارد». با `or`، به‌محضِ اینکه یک طرف تمام شود، خطِ بعدی هنوز `left[i]` و `right[j]` را با هم مقایسه می‌کند و یکی از آن دو از فهرست بیرون زده: `IndexError`.
>
> **و درسِ اصلی این است که چرا دو خطِ `extend` بعد از حلقه لازم‌اند.** حلقه عمداً زود می‌ایستد، و آن دو خط کارِ باقی‌مانده را تمام می‌کنند. اگر یکی از آن دو را حذف کنی، **هیچ خطایی نمی‌گیری و بی‌صدا عضو گم می‌کنی** — تنها راهِ گرفتنش مقایسهٔ `len` ورودی و خروجی است.

## ۷. و روی ساعت

</div>

```python
print("— merge sort (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: merge_sort(v), repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
```

```text-approx
— merge sort (زمان)
         n         زمان (ms)     نسبت به سطر قبل
     1,000               3.6                   —
     2,000               8.0                2.22
     4,000              17.6                2.21
     8,000              40.5                2.30
```

<div dir="rtl">

**ساعت همان `2.2` شمارنده را می‌گوید.** روی این ماشین، مرتب کردنِ ۸٬۰۰۰ عضو حدودِ چهل میلی‌ثانیه شد؛ `selection sort` در `n = 2,000` — یک‌چهارمِ این داده — بیش از صد میلی‌ثانیه می‌خواست.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** `merge sort` با `sorted` برای درستی، و با اعدادِ `selection sort` فصلِ ۳ برای هزینه — روی همان جنسِ ورودی و همان شمارندهٔ مقایسه. **در کدام بازهٔ `n`؟** ۱٬۰۰۰ تا ۸٬۰۰۰؛ چون `merge sort` ارزان است، بازه را نسبت به فصلِ ۳ چهار برابر بالا برده‌ایم. **با چند تکرار، و کمینه یا میانگین؟** جدول‌های شمارش یک اجرا و قطعی؛ جدولِ زمان دو تکرار به‌علاوهٔ گرم‌کننده، کمینه.

> 🤖 **از دستیارت بپرس:** «چرا کارِ هر سطح در `merge sort` مستقل از تعدادِ تکه‌های آن سطح است؟» بعد این را هم بپرس: **«اگر به‌جای دو نیمه، فهرست را به چهار تکه بشکنم، مرتبه عوض می‌شود؟»** — جوابِ درست باید بگوید نه، چون تعدادِ سطح‌ها `log₄ n` می‌شود که فقط ضریبی از `log₂ n` است. اگر دستیارت گفت «چهار برابر سریع‌تر می‌شود»، **جدولِ عمقِ بخشِ ۴ را جلویش بگذار و بپرس چند سطح کم می‌شود.**

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `merge sort` | مرج سورت | مرتب‌سازی با شکستن به دو نیمه و ادغامِ دو نیمهٔ مرتب |
| divide and conquer | دیوایْد اند کانکِر | حلِ مسئله با شکستنش به نسخه‌های کوچک‌ترِ مستقل |
| auxiliary memory | آگزیلیری مموری | حافظه‌ای که الگوریتم علاوه بر خودِ داده لازم دارد |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: کارِ هر سطح چقدر است، تعدادِ سطح‌ها چقدر، و حاصل‌ضربشان چه می‌شود؟

**تمرینِ اجباری:** `merge_sort` را طوری تغییر بده که وقتی طولِ تکه از یک حدِ مشخص کمتر شد، به‌جای شکستن، `insertion sort` فصلِ ۳ را صدا بزند. **برای چند حدِ مختلف — ۱، ۸، ۳۲، ۱۲۸ — جدولِ مقایسه و جدولِ زمان بگیر.** سؤالِ اصلی: **کدام حد بهترین زمان را داد، و آیا همان حد بهترین تعدادِ مقایسه را هم داد؟** جوابت باید توضیح بدهد چرا این دو سؤال جوابِ یکسانی ندارند.

**تمرینِ ستاره‌دار ⭐:** `merge sort` را بدونِ `recursion` بنویس: از تکه‌های یک‌عضوی شروع کن و در هر پاس، تکه‌های هم‌اندازه را دو به دو ادغام کن تا یکی بماند. **قبل از اجرا پیش‌بینی کن** تعدادِ مقایسه‌اش با نسخهٔ `recursion`دارِ همین فصل یکی درمی‌آید یا نه، بعد هر دو را در `n = 1,000` بگیر و **خطای پیش‌بینی‌ات را بنویس**. سؤالِ آخر: **کدام‌یک از این دو نسخه در `n = 200,000` کار می‌کند؟** جوابت باید به فصلِ ۱ برگردد.

## در فصل بعد

`merge sort` سریع است ولی حافظهٔ کمکی می‌خواهد. فصلِ بعد الگوریتمی می‌آورد که **همان مرتبه را بدونِ ساختنِ فهرستِ تازه** می‌گیرد — و بهایش را جای دیگری می‌پردازد.

روی ورودیِ تصادفی عالی است. ولی همان کد روی فهرستی که **از قبل مرتب باشد** به `RecursionError` می‌خورد، و وقتی درستش کنیم می‌بینیم مقایسه‌هایش در `n = 2,000` به **`1,999,000`** رسیده — **دقیقاً همان عددِ `selection sort` فصلِ ۳.** بعد با یک تغییرِ یک‌خطی همان عدد به حدودِ **`24,000`** برمی‌گردد.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t4/s04-merge-sort (یادستان, Yaadestan)
