الگوریتم مرتب‌سازی ادغام را می‌توان به صورت بازگشتی به صورت زیر توصیف کرد: الگوریتم آرایه را به دو نیمه تقسیم می‌کند و مرتب‌سازی ادغامی را بر روی هر نیمه به صورت بازگشتی اعمال می‌کند. پس از مرتب شدن دو نیمه، آنها را با هم ادغام کنید.
الگوریتم مرتب سازی ادغام در کد زیر آورده شده است:
public static void mergeSort(int[] list) {
if (list.length > 1) {
mergeSort(list[0 ... list.length / 2]);
mergeSort(list[list.length / 2 + 1 ... list.length]);
merge list[0 ... list.length / 2] with
list[list.length / 2 + 1 ... list.length];
}
}
شکل زیر نوعی ادغام آرایه ای از هشت عنصر را نشان می دهد (2 9 5 4 8 1 6 7). آرایه اصلی به (2 9 5 4) و (8 1 6 7) تقسیم می شود. مرتب سازی ادغامی را روی این دو زیرآرایه به صورت بازگشتی اعمال کنید تا (2 9 5 4) به (2 9) و (5 4) و (8 1 6 7) به (8 1) و (6 7) تقسیم شود. این فرآیند تا زمانی ادامه می یابد که زیرآرایه فقط یک عنصر را شامل شود. به عنوان مثال، آرایه (2 9) به زیر آرایه های (2) و (9) تقسیم می شود. از آنجایی که آرایه (2) حاوی یک عنصر واحد است، نمی توان آن را بیشتر تقسیم کرد. اکنون (2) را با (9) در یک آرایه مرتب شده جدید (2 9) ادغام کنید. (5) را با (4) در یک آرایه مرتب شده جدید (4 5) ادغام کنید. ادغام (2 9) با (4 5) در یک آرایه مرتب شده جدید (2 4 5 9)، و در نهایت (2 4 5 9) با (1 6 7 8) در یک آرایه مرتب شده جدید (1 2 4 5 6 7) 8 9).
فراخوانی بازگشتی به تقسیم آرایه به زیرآرایه ها ادامه می دهد تا زمانی که هر زیرآرایه فقط یک عنصر را شامل شود. سپس الگوریتم این زیرآرایه های کوچک را در زیرآرایه های مرتب شده بزرگتر ادغام می کند تا اینکه یک آرایه مرتب شده به دست آید.
الگوریتم مرتب سازی ادغام در کد زیر پیاده سازی شده است:
package demo;
public class MergeSort {
/** The method for sorting the numbers */
public static void mergeSort(int[] list) {
if(list.length > 1) {
// Merge sort the first half
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);
// Merge sort the second half
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);
// Merge firstHalf with seocndHalf into list
merge(firstHalf, secondHalf, list);
}
}
/** Merge two sorted lists */
public static void merge(int[] list1, int[] list2, int[] temp) {
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
int current3 = 0; // Current index in temp
while(current1
این mergeSort روش (خطوط 5-21) یک آرایه جدید ایجاد می کند نیمه اول، که کپی از نیمه اول است فهرست (خط 9). الگوریتم فراخوانی می کند mergeSort به صورت بازگشتی روشن نیمه اول (خط 10). طول از نیمه اول است list.length / 2 و طول نیمه دوم است list.length – list.length / 2. آرایه جدید نیمه دوم برای حاوی قسمت دوم آرایه اصلی ایجاد شد فهرست. الگوریتم فراخوانی می کند mergeSort به صورت بازگشتی روشن نیمه دوم (خط 16). بعد از نیمه اول و نیمه دوم مرتب شده اند، با هم ادغام می شوند فهرست (خط 19). بنابراین، آرایه فهرست اکنون مرتب شده است
این ادغام روش (خطوط 24-41) دو آرایه مرتب شده را ادغام می کند لیست 1 و لیست 2 به آرایه دما. جاری 1 و جاری 2 به عنصر فعلی که باید در آن در نظر گرفته شود اشاره کنید لیست 1 و لیست 2 (خطوط 25-27). این روش بارها و بارها عناصر فعلی را با هم مقایسه می کند لیست 1 و لیست 2 و کوچکتر را به دما. جاری 1 افزایش می یابد 1 (خط 31) اگر کوچکتر وارد شود لیست 1 و جاری 2 افزایش می یابد 1 (خط 33) اگر کوچکتر وارد شود لیست 2. در نهایت، تمام عناصر موجود در یکی از لیست ها به آن منتقل می شوند دما. اگر هنوز عناصر جابجا نشده در آن وجود دارد لیست 1، آنها را کپی کنید دما (خطوط 36-37). اگر هنوز عناصر جابجا نشده در آن وجود دارد لیست 2، آنها را کپی کنید دما (خطوط 39-40).
شکل زیر نحوه ادغام این دو آرایه را نشان می دهد لیست 1 (2 4 5 9) و لیست 2 (1 6 7 8). در ابتدا عناصر فعلی که باید در آرایه ها در نظر گرفته شوند 2 و 1 هستند. آنها را مقایسه کنید و عنصر کوچکتر 1 را به دما، همانطور که در شکل زیر (الف) نشان داده شده است. جاری 2 و جاری 3 1 افزایش می یابد. به مقایسه عناصر فعلی در دو آرایه ادامه دهید و عنصر کوچکتر را به دما تا زمانی که یکی از آرایه ها به طور کامل جابجا شود. همانطور که در شکل زیر (ب) نشان داده شده است، تمام عناصر در لیست 2 منتقل می شوند دما و جاری 1 به عنصر 9 اینچ اشاره می کند لیست 1. کپی 9 به دماهمانطور که در شکل زیر نشان داده شده است (ج).
این mergeSort متد دو آرایه موقت (خطوط 8، 14) را در طول فرآیند تقسیم ایجاد می کند، نیمه اول و نیمه دوم آرایه را در آرایه های موقت کپی می کند (خطوط 8، 15)، آرایه های موقت را مرتب می کند (خطوط 10، 16) و سپس آنها را در آرایه اصلی (خط 19) ادغام می کند، همانطور که در شکل زیر (الف) نشان داده شده است. می توانید کد را بازنویسی کنید تا نیمه اول آرایه و نیمه دوم آرایه را بدون ایجاد آرایه های موقت جدید به صورت بازگشتی مرتب کنید و سپس دو آرایه را در یک آرایه موقت ادغام کنید و محتویات آن را در آرایه اصلی کپی کنید، همانطور که در شکل نشان داده شده است. زیر (ب).
مرتب سازی ادغام را می توان با استفاده از پردازش موازی به طور موثر پیاده سازی کرد.
اجازه دهید T(n) زمان مورد نیاز برای مرتب‌سازی آرایه‌ای از n عنصر را با استفاده از مرتب‌سازی ادغام نشان دهد. بدون از دست دادن کلیت، فرض کنید n توان 2 باشد. الگوریتم مرتب سازی ادغام آرایه را به دو زیرآرایه تقسیم می کند، زیرآرایه ها را با استفاده از همان الگوریتم به صورت بازگشتی مرتب می کند و سپس زیرآرایه ها را ادغام می کند. از این رو،
T(n) = T(n / 2) + T(n / 2) + mergetime
T(n/2) اول زمان مرتب سازی نیمه اول آرایه و T(n/2) دوم زمان مرتب سازی نیمه دوم است. برای ادغام دو زیرآرایه، حداکثر n – 1 مقایسه برای مقایسه عناصر از دو زیرآرایه و n حرکت برای انتقال عناصر به آرایه موقت لازم است. بنابراین، کل زمان 2n – 1 است. بنابراین،
پیچیدگی مرتب سازی ادغام O(n logn) است. این الگوریتم از مرتب سازی انتخابی، مرتب سازی درج و مرتب سازی حبابی بهتر است، زیرا پیچیدگی زمانی این الگوریتم ها O(n^2) است. این مرتب سازی روش در java.util.آرایه ها کلاس با استفاده از تغییری از الگوریتم مرتب سازی ادغام پیاده سازی می شود.
