فرز بالمرج

تصغير|300بك|
مثال للتصنيف الدمجي.
**الفرز بالمَرْج** هي إحدى خوارزميات التصنيف أو ترتيب مجموعة من عناصر الرقمية تصاعديا، طورها العالم الألماني فون نيومان، تعتمد هذه الخوارزمية على مبدء «فرق تسد» ، عدد الخطوات اللازمة للخوارزمية لإنجاز المعالجة على مجموعة من مدخلات تقاس بـ N*Log N.

**خطوات الخوارزمية**
مفهوم خوارزمية التصنيف الدمجي يقوم على خطوات التالية:
# إذا كانت المصفوفة تحتوي على عنصر واحد أو أقل فإن المصفوفه مصنفة، لأنها تحتوي على عنصر واحد وبالتالي هو مصنف.
# قْسِّم كل مصفوفة غير مصنفة - أي تحتوي على أكثر من عنصر - إلى مصفوفتين.
# أعد ترتيب كل مصفوفة بطريقة الاستدعاء الذاتي recursively.
# ادمج كل مصفوتين (التي تم تريبها) إلى مصفوفة واحدة.

تعتمد الخوارزمية بشكل أساسي على مفهومين رئيسيين:
# المفهوم الأول: هو أن المصفوفات التي تحتوي على أقل عناصر يمكن ترتيبها بشكل أسرع وتحتاج إلى خطوات أقل.
# المفهوم الثاني: هو عملية دمج المصفوفات الصغيرة التي تحتوي على عناصر قليلة المرتبة لتشكيل مصفوفات أكبر مرتبة أيضا.

## تطبيق من الأعلى إلى الأسفل (Top-down)


 **function** merge_sort(*list* m)
 // if list size is 1, consider it sorted and return it
 **if** length(m)  1, so split the list into two sublists
 **var** *list* left, right
 **var** *integer* middle = length(m) / 2
 **for each** x **in** m **up to** middle
  add x to left
 **for each** x **in** m **after or equal** middle
  add x to right
 // recursively call merge_sort() to further split each sublist
 // until sublist size is 1
 left = merge_sort(left)
 right = merge_sort(right)
 // merge the sublists returned from prior calls to merge_sort()
 // and return the resulting merged sublist
 **return** merge(left, right)


في هذا المثال، الدالة `merge` تدمج المجموعتين الجزئيتين اليسرى واليمنى:


 **function** merge(left, right)
 **var** *list* result
 **while** length(left) &gt; 0 **or** length(right) &gt; 0
  **if** length(left) &gt; 0 **and** length(right) &gt; 0
  **if** first(left) 

## تطبيق من الأسفل إلى الأعلى (Bottom-up)

```c
/* array A[] has the items to sort; array B[] is a work array */
BottomUpSort(int n, array A[n], array B[n])
{
  int width;

  /* each 1-element run in A is already "sorted". */

  /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted */
  for (width = 1; width < n; width = 2 * width)
    {
      int i;

      /* array A is full of runs of length width */
      for (i = 0; i < n; i = i + 2 * width)
        {
          /* merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
          /*  or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
          BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }

      /* now work array B is full of runs of length 2*width */
      /* copy array B to array A for next iteration */
      /*   a more efficient implementation would swap the roles of A and B */
      CopyArray(A, B, n);
      /* now array A is full of runs of length 2*width */
    }
}

BottomUpMerge(array A[], int iLeft, int iRight, int iEnd, array B[])
{
  int i0 = iLeft;
  int i1 = iRight;
  int j;

  /* while there are elements in the left or right lists */
  for (j = iLeft; j < iEnd; j++)
    {
      /* if left list head exists and is <= existing right list head */
      if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
        {
          B[j] = A[i0];
          i0 = i0 + 1;
        }
      else
        {
          B[j] = A[i1];
          i1 = i1 + 1;
        }
    }
}
```

## مراجع

تصنيف:حوسبة
تصنيف:خوارزميات فرز