مرتب‌سازی ادغام یک الگوریتم مرتب سازی تطبیقی می‌باشد.
از نظر مفهومی یک الگوریتم مرتب‌سازی ادغام بدین صورت کار می‌کند:
1- اگر طول لیست ۰ یا ۱ باشد آن پیش از این مرتب شده‌است در غیر این صورت
2- لیست نامرتب را به دو زیرلیست که اندازهٔ آنها در حدود نصف سایز لیست اولیه‌است تقسیم می‌کند.
3- هر زیرلیست را به طور بازگشتی با صدا کردن merge sort مرتب می‌کند.
4- دو تا دوتا زیر لیست‌ها را از آخر ادغام می‌کند تا به یک لیست برسد.
مرتب‌سازی ادغام ۲ ایدهٔ اصلی را با هم ترکیب می‌کند تا زمان اجرایش تقویت شود.
- یک لیست کوچک از گام‌های کمتری برای مرتب‌کردن نسبت به یک لیست بزرگ استفاده می‌کند.
- یرای مرتب کردن دو لیست مرتب‌شده نسبت به دو لیست نامرتب گام‌های کمتری نیاز می‌باشد به عنوان مثال اگر این لیست‌ها مرتب باشند شما مجبور هستید تا هر لیست را فقط یکبار پیمایش کنید.
مثال: مجموعه <A=<۵،۲،۴،۷،۱،۳،۲،۶ را با استفاده از الگوریتم مرتب‌سازی ادغام مرتب کنید.
ابتدا این آرایه را نصف می‌کنیم پس دو آرایه به طول ۴ بدست می‌آید، که برابر است با (۵،۲،۴،۷) و(۱،۳،۲،۶) سپس این روال را تا جایی ادامه می‌دهیم که طول آرایه‌هایمان برابر یک شود؛ که برابر است با: (۶)(۲)(۳)(۱)(۷)(۴)(۲)(۵) حال به صورت زیر آنها را با هم ادغام می‌کنیم تا به آرایه اصلی مان برسیم.
منبع نوشته: ویکی پدیا
فایل ارائه شده، سورس کد الگوریتم مرتب سازی ادغامی با زبان برنامه نویسی C++ است.
سورس کد الگوریتم مرتب سازی ادغامی