در این فصل چه یاد میگیری#
فصلِ قبل دو الگوریتم داشت که در n = 2,000 به حدودِ دو میلیون مقایسه میرسیدند. این فصل الگوریتمی میسازد که در n = 8,000 — چهار برابرِ آن — فقط 93,704 مقایسه میخواهد، و ستونِ نسبتش بهجای 4.00 عددِ 2.19 است.
ایدهاش یک جمله است: نصف کن، هر نصف را مرتب کن، دو نصفِ مرتب را ادغام کن. و بعد میشماریم که این سرعت با چه چیزی خریده شده: در n = 8,000، صد و سه هزار و هشتصد عضو کپی میشود — حافظهای که insertion sort اصلاً لازم نداشت.

آخر این فصل میتوانی:
- دو دنبالهٔ مرتب را با یک بار عبور ادغام کنی
merge sortرا از صفر بنویسی و درستیاش را ثابت کنی- با عدد نشان بدهی که کار در هر سطح
nاست و تعدادِ سطحهاlog n - حافظهٔ کمکیاش را بشماری و بگویی چرا رایگان نیست
قبل از شروع#
از فصلِ ۱: حالتِ پایه، گامِ بازگشتی، و عمقِ call stack.
از فصلِ ۳: شمردنِ مقایسهها، و اینکه selection sort در n = 2,000 عددِ 1,999,000 میدهد. همان عدد معیارِ مقایسهٔ این فصل است.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. ادغام: هستهٔ کلِ الگوریتم#
قبل از هر recursionی، این را حل کن: دو فهرست داری که هرکدام جداگانه مرتباند. یک فهرستِ مرتب از هر دو بساز.
جوابش هیچ ربطی به مرتبسازی ندارد. کوچکترینِ نتیجه حتماً یکی از دو عضوِ اول است، پس فقط کافی است هر بار کوچکترِ آن دو را برداری و جلو بروی.
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)
چپ : [10, 14, 29, 37]
راست: [11, 13, 18, 25]
ادغام: [10, 11, 13, 14, 18, 25, 29, 37]
مقایسههای لازم: حداکثر 7
هشت عضو، حداکثر هفت مقایسه. هر مقایسه دقیقاً یک عضو را نهایی میکند، و آخرین عضو اصلاً مقایسه نمیخواهد. پس ادغام O(n) است — یک بار عبور از هر دو فهرست، و نه بیشتر.
تمامِ merge sort روی همین یک تابع سوار است. بقیهاش فقط این است که از کجا دو فهرستِ مرتب بیاوریم.
۲. و جواب: از خودمان#
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]))
[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]
اسمِ این الگو «تقسیم و حل» است و سه قدم دارد: مسئله را به دو نیمهٔ مستقل بشکن، هر نیمه را به همان روش حل کن، و جوابِ دو نیمه را به هم بچسبان.
تفاوتش با درختِ فصلِ ۲ حیاتی است. آنجا دو شاخه کارِ مشترک داشتند و همان تکرار انفجار میساخت. اینجا هر عضو دقیقاً در یکی از دو نیمه است — هیچ کارِ مشترکی نیست، پس هیچ چیزی دو بار انجام نمیشود.
۳. شمردن، در دو جهت#
حالا همان کد را با چهار شمارنده مینویسیم: مقایسه، عمق، مقایسه در هر سطح، و عضوِ کپیشده.
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"])
با sorted یکی است؟ True
مقایسه: 8709 · عمق: 11
۸٬۷۰۹ مقایسه برای هزار عضو. selection sort در همین n عددِ 499,500 میداد — پنجاهوهفت برابر بیشتر.
۴. چرا n log n: کار در هر سطح، و تعدادِ سطحها#
عددِ 8,709 را میشود شکافت، و شکافتنش کلِ استدلالِ این الگوریتم است.
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)")
سطح تعدادِ مقایسه در این سطح
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)
هر سطح حدودِ 1,000 مقایسه دارد — یعنی حدودِ n. و دلیلش روشن است: در هر سطح، تکهها با هم روی هم کلِ فهرست را میپوشانند، و ادغامِ هر تکه به اندازهٔ خودش کار دارد. پس کارِ هر سطح O(n) است، فارغ از اینکه به چند تکه شکسته شده باشد.
سطحهای پایینتر کمی کمترند چون در تکههای کوچک، احتمالِ اینکه یک طرف زودتر تمام شود بیشتر است و باقیمانده بدونِ مقایسه کپی میشود. سطحِ ۱۱ هم اصلاً در جدول نیست، چون آنجا تکهها تکعضویاند و ادغامی در کار نیست.
میماند سؤالِ دوم: چند سطح؟ هر سطح طولِ تکهها را نصف میکند، پس تعدادِ سطحها همان تعدادِ دفعاتی است که n را میشود نصف کرد تا به ۱ برسد.
🌱 ریشهاش کجاست: «چند بار میشود
nرا نصف کرد تا به ۱ برسد» تعریفِlog₂ nاست، و ریشه ترمِ ۴ فصل ۸ آن را بهعنوانِ وارونهٔ توان میسازد. نتیجهای که آنجا ساخته میشود و اینجا بهکار میآید یک جمله است:logبیرحمانه کند رشد میکند — با هزار برابر شدنِn، فقط حدودِ ده واحد بالا میرود. جدولِ عمقِ پایین دقیقاً همین را نشان میدهد.
🤔 اول حدس بزن: ستونِ نسبتِ مقایسه و ستونِ نسبتِ عمق را جدا حدس بزن. دو عدد بنویس، بعد جدول را ببین.
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")
— مقایسه
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
2.19 و رو به پایین — این امضای O(n log n) است. ترمِ ۱ فصلِ ۵ همین را در قاعدهاش نوشته بود: «کمی بالای 2 و رو به کاهش، یعنی پابهپای n بهعلاوهٔ یک لایهٔ نصفکردن». کمی بالای 2 است چون با دو برابر شدنِ n، هم کارِ هر سطح دو برابر میشود و هم یک سطحِ تازه اضافه میشود.
و جدولِ دوم آن «یک سطحِ تازه» را با چشم نشان میدهد: 11، 12، 13، 14 — هر دو برابر شدنِ n دقیقاً یکی به عمق اضافه میکند. این همان log₂ n است، بدونِ هیچ فرمولی.
حالا مدل را با اندازهگیری میسنجیم:
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}")
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
نسبت در هر چهار سطر بینِ 0.87 و 0.90 میماند و خیلی آرام بالا میرود. یعنی شمارشِ واقعی متناسب با n log₂ n است، با ضریبی کمی کمتر از یک که با بزرگ شدنِ n آرامآرام به یک نزدیک میشود. همین ماندنِ نسبت در یک بازهٔ باریک، تأییدِ مدل است — اگر مرتبه O(n²) بود این ستون با هر دو برابر شدنِ n تقریباً دو برابر میشد و اگر O(n) بود در هر سطر حدودِ ده درصد پایین میآمد؛ اینجا بالا میرود، پس نزدیکترین شکل n log n است.
۵. حافظهای که در جدولِ مقایسه دیده نمیشود#
merge یک list تازه میسازد. این یعنی merge sort — برخلافِ دو الگوریتمِ فصلِ ۳ — در جای خودِ داده کار نمیکند.
print("— عضوِ کپیشده در کلِ ادغامها (حافظهٔ کمکی)")
table([(n, sorted_stats(n)["copied"]) for n in LADDER], "عضوِ کپیشده", ",d")
— عضوِ کپیشده در کلِ ادغامها (حافظهٔ کمکی)
n عضوِ کپیشده نسبت به سطر قبل
1,000 9,976 —
2,000 21,952 2.20
4,000 47,904 2.18
8,000 103,808 2.17
ستونِ نسبتش هم 2.2 است — یعنی کلِ کپیها هم O(n log n) است. برای هزار عضو، نزدیک به ده هزار عضو کپی میشود: در هر یک از ده سطح، یک بار کلِ فهرست.
ولی این عددِ کل است، نه عددی که در یک لحظه در حافظه داری. در هر لحظه فقط ادغامهای یک شاخه باز هستند، پس بیشترین حافظهٔ همزمان O(n) است، نه O(n log n). این تفاوت را در گزارش باید صریح نوشت، وگرنه هزینه را چند برابر بزرگتر از واقع اعلام کردهای.
✅ چک کن: در تابعِ
merge_sortبخشِ ۳ — و درmergeبخشِ ۱، تا هر دو یکی بمانند — علامتِ<=را به<تغییر بده و جدولِ مقایسهٔ بخشِ ۴ را دوباره بگیر. (جدولِ بخشِ ۴ ازmerge_sortمیآید، که حلقهٔ ادغام را داخلِ خودش دارد؛ اگر فقطmergeرا عوض کنی هیچ اتفاقی نمیافتد.) جواب همچنان باsortedیکی درمیآید و ستونِ نسبت هم عوض نمیشود — چون دادههای ما تکراری ندارند. این تغییر بیخطر بهنظر میرسد و نیست: فصلِ ۸ نشان میدهد که همین یک نویسه، روی دادهای که عضوِ برابر دارد، خاصیتی را از بین میبرد که کلِ مرتبسازیِ چندکلیدی روی آن سوار است.
۶. یک نویسه در شرطِ حلقه#
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}")
IndexError: list index out of range
🔧 اگر کار نکرد:
andمیگوید «تا وقتی هر دو طرف عضوی دارند»،orمیگوید «تا وقتی دستِکم یکی عضوی دارد». باor، بهمحضِ اینکه یک طرف تمام شود، خطِ بعدی هنوزleft[i]وright[j]را با هم مقایسه میکند و یکی از آن دو از فهرست بیرون زده:IndexError.و درسِ اصلی این است که چرا دو خطِ
extendبعد از حلقه لازماند. حلقه عمداً زود میایستد، و آن دو خط کارِ باقیمانده را تمام میکنند. اگر یکی از آن دو را حذف کنی، هیچ خطایی نمیگیری و بیصدا عضو گم میکنی — تنها راهِ گرفتنش مقایسهٔlenورودی و خروجی است.
۷. و روی ساعت#
print("— merge sort (زمان)")
table([(n, 1000 * clock(lambda v=shuffled[n]: merge_sort(v), repeat=2))
for n in LADDER], "زمان (ms)", ",.1f")
— 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
ساعت همان 2.2 شمارنده را میگوید. روی این ماشین، مرتب کردنِ ۸٬۰۰۰ عضو حدودِ چهل میلیثانیه شد؛ selection sort در n = 2,000 — یکچهارمِ این داده — بیش از صد میلیثانیه میخواست.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟
merge sortباsortedبرای درستی، و با اعدادِselection sortفصلِ ۳ برای هزینه — روی همان جنسِ ورودی و همان شمارندهٔ مقایسه. در کدام بازهٔn؟ ۱٬۰۰۰ تا ۸٬۰۰۰؛ چونmerge sortارزان است، بازه را نسبت به فصلِ ۳ چهار برابر بالا بردهایم. با چند تکرار، و کمینه یا میانگین؟ جدولهای شمارش یک اجرا و قطعی؛ جدولِ زمان دو تکرار بهعلاوهٔ گرمکننده، کمینه.
🤖 از دستیارت بپرس: «چرا کارِ هر سطح در
merge sortمستقل از تعدادِ تکههای آن سطح است؟» بعد این را هم بپرس: «اگر بهجای دو نیمه، فهرست را به چهار تکه بشکنم، مرتبه عوض میشود؟» — جوابِ درست باید بگوید نه، چون تعدادِ سطحهاlog₄ nمیشود که فقط ضریبی ازlog₂ nاست. اگر دستیارت گفت «چهار برابر سریعتر میشود»، جدولِ عمقِ بخشِ ۴ را جلویش بگذار و بپرس چند سطح کم میشود.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
merge sort |
مرج سورت | مرتبسازی با شکستن به دو نیمه و ادغامِ دو نیمهٔ مرتب |
| divide and conquer | دیوایْد اند کانکِر | حلِ مسئله با شکستنش به نسخههای کوچکترِ مستقل |
| auxiliary memory | آگزیلیری مموری | حافظهای که الگوریتم علاوه بر خودِ داده لازم دارد |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
merge sort سریع است ولی حافظهٔ کمکی میخواهد. فصلِ بعد الگوریتمی میآورد که همان مرتبه را بدونِ ساختنِ فهرستِ تازه میگیرد — و بهایش را جای دیگری میپردازد.
روی ورودیِ تصادفی عالی است. ولی همان کد روی فهرستی که از قبل مرتب باشد به RecursionError میخورد، و وقتی درستش کنیم میبینیم مقایسههایش در n = 2,000 به 1,999,000 رسیده — دقیقاً همان عددِ selection sort فصلِ ۳. بعد با یک تغییرِ یکخطی همان عدد به حدودِ 24,000 برمیگردد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.