به نام خدا

یکی از بهترین انواع مرتب سازی روش merg sort می باشد. برای درک بهتر، این قسمت را با یک مثال آموزش می دهیم:

می خواهیم لیست روبه­ رو را به روش merge sort  مرتب کنیم : 8,2,4,6,9,7,10,1,5,3

merge sort با قسمت کردن و جدا کردن لیست به دو قسمت، با اعضا منحصر بفرد به صورت متوالی شروع می­ شود:

حال این لیست ها را به صورت دوتایی مرتب می کنیم  تا به لیست اصلی برسیم، شکل زیر نشان دهنده این موضوع است:

برای انجام merge sort  ما یک لیست را به 2 تا زیرلیست که اندازه آنها ( طول آنها ) تقریباً یکسان هستند تقسیم می­کنیم. هر کدام از زیر لیستها را با استفاده از اگوریتم merge sort مرتب می­کنیم، سپس دو زیر لیست را به هم می چسبانیم. برای این کار ابتدا تابعی به نام merge تعریف می کنیم که در آن یک آرایه را با گرفتن اندیس ابتدا و انتها به دو قسمت با طول مساوی تقسیم می کند:

void merge(int arr[ ] , int low, int high){
int mid=(low+high)/2;
   int j = low;
   for (int i = mid + 1 ; i <= high ; i++){
       while (arr[ j ] <= arr[ i ] && j < i)
           j++;
       if (j == i)
           break;
       int t = arr[ i];
       for (int k = i ; k > j ; k--)
           arr[ k ] = arr[k-1];
       arr[ j ] = t;
   }//end for i
}//end merge 

سپس تابعی دیگر تعریف می کنیم تا با استفاده از تابع قبلی آرایه منظم شده را به ما ارائه دهد.

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  , high);
}//end merge_sort

 

در واقع ابتدا آرایه را تا حد ممکن خرد می کنیم و وقتی دوباره می خواهیم آن ها را بهم بچسبانیم یا به اصطلاح merge کنیم این کار را بر اساس بزرگتر و کوچک تر بودن اعداد انجام می دهیم. به این ترتبب در انتها آرایه مرتب خواهد شد.

در این الگوریتم پیچیدگی در بهترین و بدترین حالت برابر است با n*logn

برای دانلود این الگوریتم در یک برنامه می توانید روی لیک زیر کلیک نمایید:

دانلود سورس کد و فایل اجرایی برنامه مرتب سازی به روش Merge Sort به صورت رایگان با لینک مستقیم