ايران ويج

با سلام اگر کسی توضیحاتی در مورد الگوریتم مرتب سازی ادغامی داره برام بزاره با احترام اگر کدهاشو رو هم دارید ممنون می شم

اگه برای مرتب کردن میخواید میگن quicksort بهتره.

توی مرتب سازی ادغامی میایم اول لیستو دو نصفش میکنیم. بعد هر دو تا نصفه رو دوباره میدیم به خودش ( بازگشتیه ) و در نهایت پیش میریم تا به تک عضوی برسیم. بعد میایم این نصفه ها رو دوباره میدیم به یه تابع دیگه که دو تا نصفه به صورت مرتب به هم میچسبونه و یه لیست مرتب شده در نهایت بیرون میاد. شبه کدشو دارم:
این تابع اصلی :

کد: 
void mergesort (int n, keytype s[])

{

   const int h = [n/2] , m = n - h;

   keytype U[1..h], v[1..m];

   if (n > 1){

     copy S[1] through S[h] to U[1] through U[h];

     copy S[h + 1] through S[n] to V[1] through U[m];

     mergesort(h, U);

     mergesort(m, V);

     merge(h, m, U, V, S);

   }

}

اینم چسبونکش:

کد: 
void merge (int h, int m, const keytype U[], Const keytype V[], keytype S[])

{

   index i,j,k;

   i = 1; j = 1 k = 1;

   while (i <= h && j <= m) {

     if (U[i] < V[j]) {

       S[k] = U[i];

       i++;

     }

     else {

       S[k] = V[j];

       j++;

     }

     k++;

   }

   if (i > h)

     copy V[j] through V[m] to S[k] through S[h + m];

   else

     copy U[i] through U[h] to S[k] through S[h + m];

}

البته این درجا نیست و حافظه زیاد میسوزونه. در نتیجه بهتره برای لیستای بزرگ و کوچیک از مدل 2 استفاده کنید:

کد: 
void mergesort2 (index low, index high)

{

   index mid;

   if (low < high) {

     mid = [(low + high)/2];

     mergesort2(low, mid);

     mergesort2(mid + 1, high);

     merge2(low, mid, high);

   }

}

اینم چسبونکش:

کد: 
void merge2(index low, index mid, index high)

{

   index i, j, k;

   keytype U[low..high];

   i = low; j = mid+1; k = low;

   while (i <= mid && j <= high) {

     if (S[i] < S[j]) {

       U[k] = S[i];

       i++;

     }

     else {

       U[k] = S[j];

       j++;

     }

     k++;

   }

   if (i > mid)

     move S[j] through S[high] to U[k] through U[high];

   else

     move S[i] through S[mid] to U[k] through U[high]

   move U[low] through S[mid] to U[k] through U[high];

}

mobilemasoud

ajlajlajl