فرز بالمرج

مثال للتصنيف الدمجي.
الفرز بالمَرْج هي إحدى خوارزميات التصنيف أو ترتيب مجموعة من عناصر الرقمية تصاعديا، طورها العالم الألماني فون نيومان، تعتمد هذه الخوارزمية على مبدء «فرق تسد» ، عدد الخطوات اللازمة للخوارزمية لإنجاز المعالجة على مجموعة من مدخلات تقاس بـ N*Log N.V. J. Duvanenko, "Parallel Merge Sort", Dr. Dobb's Journal, March 2011 

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

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

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

 function merge_sort(list m)
 // if list size is 1, consider it sorted and return it
 if length(m) <= 1
  return m
 // else list size is > 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) > 0 or length(right) > 0
  if length(left) > 0 and length(right) > 0
  if first(left) <= first(right)
   append first(left) to result
   left = rest(left)
  else
   append first(right) to result
   right = rest(right)
  else if length(left) > 0
   append first(left) to result
    left = rest(left)
   else if length(right) > 0
    append first(right) to result
    right = rest(right)
  end while
  return result

 تطبيق من الأسفل إلى الأعلى (Bottom-up) 
/* 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;
        }
    }
}
 مراجع 

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