مرتب‌سازی ادغامی

تقسیم و حل
بازگشتی

آرایه را از وسط دو نیم می‌کند، هر نیمه را به‌صورت بازگشتی مرتب می‌کند و دو نیمه‌ی مرتب را در هم ادغام می‌کند.

مرتب‌سازی ادغامی نمونه‌ی کلاسیک «تقسیم و حل» است:

ادامه‌ی توضیح ↓

زمان: O(n log n)
حافظه: O(n)
CLRS، بخش ۲.۳
هوروویتز–ساهنی، فصل ۷
جانسون‌باو، فصل ۷

ورودی:

n=8خروجی PDF

هشت عدد درهم: سه سطح تقسیم و هفت ادغام.

def merge_sort(a):
sort(a, 0, len(a) - 1)
return a
def sort(a, lo, hi):
if lo >= hi:
return
mid = (lo + hi) // 2
sort(a, lo, mid)
sort(a, mid + 1, hi)
merge(a, lo, mid, hi)
def merge(a, lo, mid, hi):
left = a[lo:mid + 1]
right = a[mid + 1:hi + 1]
i = 0
j = 0
k = lo
while i < len(left) and j < len(right):
if left[i] <= right[j]:
a[k] = left[i]
i = i + 1
else:
a[k] = right[j]
j = j + 1
k = k + 1
while i < len(left):
a[k] = left[i]
i = i + 1
k = k + 1
while j < len(right):
a[k] = right[j]
j = j + 1
k = k + 1

ناوردا: در حلقه‌ی merge، خانه‌های a[lo..k−1] کوچک‌ترین عضوهای left و right را به ترتیب دارند.

شروع اجرا

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

نارنجی = در همین گام عوض شد

`a` list

52471326

Call stack

merge_sort()خط 1

گام ۱ از ۲۴۵

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

comparisons
write
ورودی فعلی (n=8)

نمایش به شکل جدول

n	comparisons	write
4	4.8	8
6	9.7	16
8	15.3	24
10	22.2	34
12	30.1	44
14	37.7	54
16	45.3	64

توضیح

ایده

مرتب‌سازی ادغامی نمونه‌ی کلاسیک «تقسیم و حل» است:

تقسیم: بازه‌ی a[lo..hi] را از وسط (mid) دو نیم کن.
حل: هر نیمه را با همین الگوریتم، به‌صورت بازگشتی مرتب کن. بازه‌ی یک‌عضوی خودبه‌خود مرتب است.
ترکیب: دو نیمه‌ی مرتب را در هم ادغام کن.

ادغام

دو نیمه در left و right کپی می‌شوند. در هر گام، کوچک‌ترین عضو باقی‌مانده‌ی دو طرف با یک مقایسه پیدا و در a[k] نوشته می‌شود. وقتی یکی از دو طرف تمام شد، بقیه‌ی طرف دیگر بدون مقایسه کپی می‌شود.

هزینه

عمق بازگشت log n است و در هر سطح، کل آرایه یک بار ادغام می‌شود، پس زمان در همه‌ی حالت‌ها O(n log n) است.
ادغام به آرایه‌ی کمکی نیاز دارد، پس حافظه‌ی اضافه O(n) است.
تعداد مقایسه‌ها به ورودی بستگی دارد: برای ۸ عضو بین ۱۲ (آرایه‌ی مرتب) و ۱۷ (ورودی درهم‌تنیده).

پایداری

با شرط left[i] ≤ right[j]، از دو عضو برابر همیشه آنکه از نیمه‌ی چپ آمده اول نوشته می‌شود، پس ترتیب عضوهای برابر حفظ می‌شود و مرتب‌سازی پایدار است.

در trace به چه چیزی نگاه کنی

نوار آبی پشت میله‌ها بازه‌ی lo..hi فراخوانی جاری است.
«درخت فراخوانی‌های بازگشتی» زیر تصویر نشان می‌دهد کدام زیرمسئله در حال اجراست و کدام‌ها تمام شده‌اند.
با سطح جزئیات «هر دور حلقه» فقط گام‌های تقسیم را ببین؛ با «هر عملیات» ادغام را مقایسه‌به‌مقایسه دنبال کن.