مرتب ساز ادغامی

تحلیل الگوریتم

در واقع ابتدا به ما آرایه‌ای غیر مرتب با طول n داده می‌شود که آن را به دو زیر آرایه با طول مساوی n/۲ تقسیم می‌کند.
و ابن تقسیم را به صورت بازگشتی برای هر کدام از آن بخش‌ها ادامه می‌دهد.هنگامی که توالی که باید مرتب شود طولی برابر ۱ داشته باشد بازگشت خاتمه می‌یابد که در این حالت کاری برای انجام شدن وجود ندارد چون هر توالی با طول ۱ در واقع به صورت بدیهی مرتب شده‌است و حالا می‌خواهیم هر دو دسته را با هم مرتب کنیم.در واقع هر دسته در درون خود مرتب است و ما می‌خواهیم از آن دو یک دستهٔ ادغام شدهٔ مرتب بسازیم.گام اصلی ما تشکیل شده‌است از انتخاب عدد کوچکتر از بین دو عدد اول هر خانه قرار دادن آن در آرایهٔ اصلی و حذف آن از زیر آرایهٔ فعلی و ادامهٔ کار.هر گام زمان ثابتی را صرف می‌کند و چون حداکثر n گام اصلی را اجرا می‌کنیم زمان(Θ(n را برای merge کردن صرف می‌کنیم و چون تداد زیر شاخه‌ها تا رسیدن به زیر شاخه‌ای با طول یک برابر logn است کل زمان اجرا برابر (Θ(nlogn است .

زمان اجرا

اگر بخواهیم زمان اجرا را به صورت درختی محاسبه کنیم در زیر خواهیم داشت:
T(n) = T( n/2 ) + T( n/2 ) + θ(n
که برای سادگی:
T(n) = 2T (n/2) + θ(n
]

نحوهٔ پیاده سازی الگوریتم

void mergeSort(int numbers[], int temp[], int array_size){
  m_sort(numbers, temp, 0, array_size - 1);}void m_sort(int numbers[], int temp[], int left, int right){
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, mid+1, right);

    merge(numbers, temp, left, mid+1, right);
  }}void merge(int numbers[], int temp[], int left, int mid, int right){
  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;
  tmp_pos = left;
  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos = tmp_pos + 1;
      left = left +1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos = tmp_pos + 1;
      mid = mid + 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left = left + 1;
    tmp_pos = tmp_pos + 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid = mid + 1;
    tmp_pos = tmp_pos + 1;
  }

  for (i=0; i < num_elements; i++)
  {
    numbers[right] = temp[right];
    right = right - 1;
  }}

و مثالی از شبه کدی دیگر به زبان C

#include<;stdio.h>
 
#define SIZE 100
 
void mergesort(int, int a[]);int main(){
    int a[SIZE];
    int i, n;
 
    printf("No of elements to be sorted:\n");
    scanf("%d",&n);
    printf("Enter the elements:\n");
    for(i=0;i<n;i++)
    scanf("%d",&;a[i]);
    printf("Unsorted list:\n");
    for(i=0;i<n;i++)
    printf("%d",a[i]);
    printf("\n");
    mergesort(n, &;a);
    printf("Sorted list:\n");
    for(i=0;i<n;i++)
    printf("%d ",a[i]);
    printf("\n");
    return 0;}void mergesort(int n, int a[]){
    int n1, n2, i, j, k;
    int a1[n];
    int *a2, *a3;
    for (i=0;i<n;i++)
    a1[i] = a[i];
    if (n%2 == 0)
    n1 = n/2;
    else
    n1 = n/2 + 1;
    n2 = n - n1;
    if (n >; 2)
    {
    mergesort(n1, &;a1);
    mergesort(n2, &;a1[n1]);
    }
    j = k = 0;
    a2 = &a1;
    a3 = &;a1[n1];
    for (i=0;i<n;i++)
    {
    if (k == n2)
    {
        a[i] = *(a2+j);
        j++;
    }
    else if (j == n1)
    {
        a[i] = *(a3+k);
        k++;
    }
    else if(*(a2+j) <;= *(a3+k))
    {
        a[i] = *(a2+j);
        j++;
    }
    else
    {
        a[i] = *(a3+k);
        k++;
    }
    }}

شبه کد مرتب سازی ادغام به زبان پاسکال

Procedure Merg(idxLow, idxMid, idxHigh: Integer);Var
  i, j, h, k: Integer;Begin
  h := idxLow;
  i := idxLow;
  j := idxMid + 1;

  While ((h <= idxMid) And (j <= idxHigh)) Do
    Begin
      If (A[h] < A[j]) Then
        Begin
          B[i] := A[h];
          h := h + 1;
        End
      Else
        Begin
          B[i] := A[j];
          j := j + 1;
        End;
      i := i + 1;
    End;

  If (h > idxMid) Then
    Begin
      For k := j To idxHigh Do
        Begin
          B[i] := A[k];
          i := i + 1;
        End;
    End
  Else
    Begin
      For k := h To idxMid Do
        Begin
          B[i] := A[k];
          i := i + 1;
        End;
    End;

  For k := idxLow To idxHigh Do
    A[k] := B[k];End;Procedure MSort(Low_IDX, High_IDX: Integer);Var
  Mid_IDX: Integer;Begin
  If (Low_IDX < High_IDX) Then
    Begin
      Mid_IDX := (Low_IDX + High_IDX) Div 2;

      MSort(Low_IDX, Mid_IDX);
      MSort(Mid_IDX + 1, High_IDX);
      Merg(Low_IDX, Mid_IDX, High_IDX);
    End;End;