درخواست توضیح در مورد الگوریتم ادغامی

[mobilemasoud]

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

[ajlajlajl]

اگه برای مرتب کردن میخواید میگن 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];
}