الگوریتم ادغام
الگوریتم‌های ادغام الگوریتم‌هایی هستند که چند آرایهٔ مرتب را به عنوان ورودی دریافت می‌کنند و آرایه‌ای مرتب متشکل از اعضای کلیهٔ آرایه‌های ورودی را خروجی می‌دهند. از این الگوریتم به عنوان زیرروال در الگوریتم‌های مرتب‌سازی استفاده می‌شود.
ادغام دو لیست در زمان اجرای خطی و با حافظهٔ اضافی خطی قابل انجام است. کد زیر در زبان پایتون این عملیات را نشان می‌دهد. در این کد با گرفتن آرایه‌ای خالی به عنوان آرایهٔ جواب عملیات را آغاز می‌کنیم. با شروع از ابتدای دو آرایهٔ ورودی و با مقایسه اعضای آن‌ها به ترتیب، عضو کوچکتر را به آرایهٔ جواب می‌افزاییم. در آخر اعضایی از یک آرایهٔ ورودی باقی می‌ماند؛ آن‌ها را نیز به همان ترتیب به آرایهٔ جواب می‌افزاییم.
def merge(a,b): می‌خواهیم الگوریتمی ارائه دهیم که به عنوان ورودی formula_1 آرایهٔ مرتب را بگیرد و آرایه‌ای مرتب از کلیهٔ اعضای آن‌ها را خروجی دهد. ادغام formula_1 آرایه مرتب، در الگوریتم‌های مرتب‌سازی بسیاری از جمله مرتب‌سازی شکیبانه و مرتب‌سازی خارجی استفاده می‌شود.
برای ادغام formula_1 آرایه یا لیست مرتب چندین الگوریتم وجود دارد که در اینجا به ۳ مورد از آن‌ها اشاره می‌کنیم.
یک الگوریتم ساده اما طولانی این است که همانند روشی که برای دو لیست عمل کردیم، با شروع از ابتدای همه لیست‌ها، کمینه را پیدا کرده و آن را به آرایهٔ جواب اضافه نموده و این عمل تا زمانی که کل لیست‌ها خالی شوند، تکرار می‌کنیم. زمان اجرای این الگوریتم، formula_5 است.
در این الگوریتم، ابتدا لیست اول را با لیست دوم ادغام می‌کنیم، سپس حاصل را با لیست سوم ادغام می‌کنیم و همین گونه ادامه می‌دهیم تا به یک لیست نهایی برسیم. چون زمان اجرای ادغام دو لیست با formula_6 عضو در کل، formula_7 است، بنابراین زمان اجرای این الگوریتم برابر است با:
formula_8
در محاسبه زمان فرض شده‌است تعداد اعضای همهٔ لیست‌ها برابر و تعداد کل اعضا formula_6است. در این صورت اعضای لیست اول و دوم در کلیه ادغام‌ها یعنی formula_10 ادغام، اعضای لیست سوم از ادغام دوم به بعد یعنی در formula_11 ادغام و به همین ترتیب تا لیست آخر در ادغام آخر حضور دارند. اعضای هر لیست را به تعداد تکرار آن‌ها در ادغام‌ها باید بشماریم که در عبارت بالا انجام شده‌است.
برای سریع‌تر انجام دادن این عملیات، از هرم کمینه استفاده می‌کنیم. ابتدا با استفاده از عضو اول همهٔ لیست‌ها، یک هرم کمینه می‌سازیم. این عمل می‌تواند در زمان اجرای formula_7 انجام شود. سپس هربار کمینه که عضو اول هرم است را خروجی داده و عضو بعدی آرایه شامل آن را جایگزینش می‌کنیم (اگر عضو بعدی نداشت، بی‌نهایت را جایگزین آن می‌کنیم). سپس باید دوباره هرم را به هرم کمینه تبدیل کنیم که این کار زمان اجرای formula_13 را داراست. اگر در کل formula_6عدد در کل لیست‌ها داشته باشیم، کل عملیات دارای زمان اجرای formula_15 خواهد بود.
الگوریتم زیر در زبان پایتون چگونگی این ادغام را نشان می‌دهد. ورودی‌های این تابع، دو آرایهٔ مرتب formula_16 به طول formula_6 و formula_18 به طول formula_19 است و خروجی آرایهٔ formula_20 به طول formula_21 است. به این ادغام، موازی گویند چرا که دو خط نهایی تابع زیر، ورودی‌هایی کاملاً جدا از هم دارند پس می‌توانند به‌طور موازی انجام شوند. از این ادغام در استفاده می‌شود. (در این الگوریتم از جستجوی دودویی استفاده‌شده‌است) def parallel_merge(A, B, C):
مهم‌ترین کاربرد این الگوریتم در مرتب‌سازی ادغامی است. این مرتب‌سازی، یک مرتب‌سازی مقایسه‌ای است که از الگوریتم تقسیم و حل استفاده می‌کند. به این گونه که به‌طور بازگشتی، آرایه را به دو آرایه با طول مساوی تقسیم می‌کند تا به آرایه‌هایی با طول یک برسد. سپس به‌طور بازگشتی آرایه‌ها را باهم ادغام می‌کند تا در نهایت به یک آرایهٔ مرتب‌شده برسد. مثالی از این مرتب‌سازی را در تصویر مشاهده می‌کنید.
کاربرد دیگر این الگوریتم در مرتب‌سازی شکیبانه است. این مرتب‌سازی که در واقع از یک بازی کارتی گرفته شده‌است، به این گونه عمل می‌کند: فرض کنید formula_6 کارت با شماره‌های یک تا formula_6 با ترتیبی دلخواه داریم. اولین کارت را روی میز قرار داده و اولین کپه کارت را می‌سازیم. بعد از آن در هر مرحله، کارت جدید یا به چپ‌ترین کپه‌ای اضافه می‌شود که کارت سر آن کپه دارای عددی بزرگتر یا مساوی عدد کارت جدید باشد یا در راست همهٔ کپه‌ها به عنوان کپه‌ای جدید قرار می‌گیرد. در این صورت بعد از تمام شدن کارت‌ها، تعدادی کپه کارت داریم که در هر کپه اعداد کارت از پایین کپه به بالا نزولی‌اند و کافیست برای مرتب‌سازی کل کارت‌ها این کپه‌ها را باهم ادغام کنیم. (ادغام formula_1 لیست)
از این الگوریتم در مرتب‌سازی خارجی نیز استفاده می‌شود. از مرتب‌سازی خارجی برای مرتب کردن اطلاعات فایل‌ها هنگامی که حافظهٔ اصلی یا RAM محدود است، بهره می‌گیریم. این گونه عمل می‌کنیم که در هر مرحله مقداری از فایل که در حافظهٔ اصلی می‌تواند قرار گیرد را برداشته، توسط یک الگوریتم مرتب‌سازی، مرتب نموده و در حافظهٔ خارجی مثلاً Hard Drive قرار می‌دهیم. در نهایت بخش‌های مرتب‌شدهٔ فایل را باهم ادغام می‌کنیم.