مرتب‌سازی ادغامی (Merge Sort)

مرتب‌سازی ادغامی: الگوریتم تقسیم و حل با تضمین O(n log n)، فرایند merge و کاربردهای واقعی

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

Merge Sort الگوریتم تقسیم و حل (Divide and Conquer) است:

  1. تقسیم: لیست را از وسط نصف کن (بازگشتی)
  2. حل: هر نصف را مرتب کن (تا طول ۱ — تک عنصر مرتب است!)
  3. ادغام: دو نصف مرتب را با هم ترکیب کن

قلب الگوریتم: Merge

ادغام دو لیست مرتب آسان است: دو اشاره‌گر، هر بار کوچک‌ترین سرِ دو لیست را بردار:

چپ: [2, 5, 8]   راست: [1, 4, 9]
مقایسه سرها: 2 و 1 -> 1
مقایسه: 2 و 4 -> 2
مقایسه: 5 و 4 -> 4
... نتیجه: [1, 2, 4, 5, 8, 9]

مثال کامل

[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]
ادغام:  [27, 38] [3, 43]  [9, 82] [10]
ادغام:  [3, 27, 38, 43]   [9, 10, 82]
ادغام:  [3, 9, 10, 27, 38, 43, 82]  ✓

پیچیدگی

معیارمقدار
زمان (همه حالات)O(n log n) ✓ تضمینی!
حافظهO(n) — آرایه کمکی
پایدار✓ بله

چرا n log n؟ log n سطح تقسیم داریم و هر سطح n عملیات ادغام می‌خواهد.

مزیت بزرگ: تضمین

برخلاف Quick Sort که بدترین حالتش O(n²) است، Merge Sort همیشه O(n log n) است — قابل پیش‌بینی! به همین دلیل در سیستم‌های real-time محبوب است.

کاربردهای واقعی

نکته: معیار حافظه: Merge حافظه اضافی O(n) می‌خواهد؛ اگر حافظه بحرانی است، Quick Sort (حافظه O(log n)) بهتر است.

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.

ابزارهای مرتبط