روش مرتب‌سازی ادغامی (Merge Sort) یک روش مرتب‌سازی مبتنی بر مقایسه عناصر با استفاده از روش تقسیم و غلبه است. این روش از مراحل بازگشتی زیر تشکیل یافته است:
1- آرایه را به دو زیرآرایه با اندازه تقریبا یکسان تقسیم کن.
2- دو زیرآرایه را به روش مرتب‌سازی ادغامی مرتب کن.
3- دو زیرآرایه مرتب‌شده را ادغام کن.
پیاده‌سازی مرتب‌سازی ادغامی
[برگرد بالا]
بر اساس توضیحات فوق قطعه کدهای زیر به زبان‌های برنامه‌نویسی ++C و Python الگوریتم مرتب‌سازی ادغامی را پیاده‌سازی می‌کنند.
void merge_sort(int arr[], int low, int high){
if(low >= high)
return;
int mid = (low + high) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
def merge_sort(arr, low, high):
if low >= high:
return
mid = (low + high) / 2
merge_sort(arr, low, mid)
merge_sort(arr, mid + 1, high)
merge(arr, low, mid, high)
این قطعه کدها بازه‌های low تا mid و mid + 1 تا high را به صورت بازگشتی مرتب کرده و سپس توسط تابع merge ادغام می‌کنند. به این ترتیب آرایه arr از بازه low تا high مرتب می‌شود.
تابع merge پیاده‌سازی‌های مختلفی دارد. یک روش ساده آن است که ادغام دو زیرآرایه در یک آرایه کمکی به طول مجموع طول‌های این دو زیرآرایه صورت بگیرد. در این حالت این مرتب‌سازی یک مرتب‌سازی درجا نخواهد بود. چرا که متناسب با طول آرایه نیاز به فضای اضافی جهت مرتب‌سازی وجود دارد.
قطعه کد زیر یک پیاده‌سازی درجا برای تابع merge است.
void merge(int arr[], int low, int mid, int high){
int i, j, k, t;
j = low;
for(i = mid + 1 ; i <= high ; i++){
while(arr[j] <= arr[i] && j < i)
j++;
if(j == i)
break;
t = arr[i];
for(k = i ; k > j ; k --)
arr[k] = arr[k - 1];
arr[j] = t;
}
}
def merge(arr, low, mid, high):
j = low
for i in range(mid + 1, high + 1):
while arr[j] <= arr[i] and j < i:
j +=1
if j == i:
break
t = arr[i]
for k in range(i, j, -1):
arr[k] = arr[k - 1]
arr[j] = t
این تابع محل مناسب عناصر زیرآرایه سمت راست را در زیرآرایه سمت چپ پیدا کرده و در آن درج میکند. با توجه به این که عناصر دو زیرآرایه مرتب هستند، ادغام آنها پیچیدگی کمتری خواهد داشت.
به عنوان مثال اگر هدف ادغام کردن زیرآرایه‌های زیر باشد:
1 3 6 9 / 2 4 5 8
ترتیب چینش عناصر پس از اتمام هر تکرار حلقه بیرونی قطعه کد فوق، به این ترتیب خواهد بود:
1) 1 3 6 9 / 2 4 5 8 → 1 2 3 6 9 / 4 5 8
2) 1 2 3 6 9 / 4 5 8 → 1 2 3 4 6 9 / 5 8
3) 1 2 3 4 6 9 / 5 8 → 1 2 3 4 5 6 9 / 8
4) 1 2 3 4 5 6 9 / 8 → 1 2 3 4 5 6 8 9 /
پیچیدگی زمانی مرتب‌سازی ادغامی
[برگرد بالا]
تعداد عناصر آرایه را $n$ و تعداد مقایسه‌های مورد نیاز جهت مرتب‌سازی این عناصر را $T(n)$ در نظر می‌گیریم.
بر اساس تعریف بازگشتی این الگوریتم، مرتب کردن $n$ عنصر نیاز به مرتب شدن دو زیر آرایه تقریبا $\frac{n}{2}$ عنصری دارد. پس از این مرحله، این دو زیرآرایه توسط تابع merge ادغام می‌شوند.
جهت ادغام دو زیرآرایه با قطعه کد فوق - که در مجموع $n$ عنصر دارند - حداکثر $n$ مقایسه اتفاق خواهد افتاد. پس می‌توان نوشت:
\[T(n) = 2 T(\frac{n}{2}) + n \]
حل این رابطه بازگشتی نشان از مرتبه اجرای $ \theta(n log n) $ دارد. اما درجا بودن کد باعث می‌شود در بدترین شرایط مرتبه جابجایی‌ها $ \theta (n^2) $ باشد (چرا؟). پیاده‌سازی غیردرجا این کمک را میکند که بتوان با $ \theta (n) $ جابجایی ادغام را انجام داد.
حافظه مصرفی مرتب‌سازی ادغامی
[برگرد بالا]
حافظه مازاد مورد نیاز برای این الگوریتم به روش پیاده‌سازی مرحله ادغام بستگی دارد. قطعه کد فوق این قسمت را به روش درجا پیاده‌سازی میکند. اما روش‌های ساده‌تری وجود دارند که عمل ادغام را روی حافظه دیگری غیر از حافظه تخصیص یافته به خود آرایه انجام می‌دهند. چنین الگوریتم‌هایی از نظر هزینه زمانی پیچیدگی کمتری دارند. اما برای یک آرایه به طول $n$ نیاز به آرایه مجزایی به همان اندازه برای ادغام دارند.
ویژگی‌های مرتب‌سازی ادغامی
[برگرد بالا]
مرتب‌سازی ادغامی ویژگی‌های زیر را دارد:
1- پیچیدگی زمانی اجرای الگوریتم در تمامی حالات $\theta (n log n) $ است؛ چرا که این الگوریتم تحت هر شرایطی آرایه را به دو قسمت کرده و مرتب‌سازی را انجام می‌دهد.
2- پیچیدگی حافظه مصرفی بستگی به روش پیاده‌سازی مرحله ادغام دارد که تا $ O(n) $ افزایش میابد. پیاده‌سازی درجای این الگوریتم حافظه مصرفی مرتبه $ \theta (1) $ دارد؛ اما اجرای آن در بدترین حالت زمان‌بَر است.
3- الگوربتم مرتب‌سازی ادغامی با پیاده‌سازی فوق یک روش پایدار است. چنین الگوریتمی ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ میکند.