Metode Merge Sorting dalam bahasa C

Metode merge sort merupakan metode sorting dengan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian, kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.

Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

berikut sources code dalam bahasa C

fungsi main

#include"stdio.h";
#include"stdlib.h";
#define max 10000

void input();
void tukar(int *, int *);
void tampil();
void partisi(int data[],int low,int high);
void mergesort(int data[],int low,int mid,int high);
int data[max],hasil[max];
int n;

int main()
{

 input();
 awal=0; akhir=n-1;
        partisi(data,awal,akhir);
 tampil();
 
}

fungsi input

void input()
{
 int i;
 printf("Masukkan jumlah total elemen: ");
    scanf("%d",&n);

    puts(" ");
    for(i=0;i<n;i++)
 {
  data[i]=rand();
  printf("%d\t",data[i]);
  //printf("Elemen ke-%d: ",i+1);
        //scanf("%d",&data[i]);
    }
}

fungsi mergesort

void partisi(int data[],int low,int high)
{
    int mid;

    if(low<high)
 {
         mid=(low+high)/2;
         partisi(data,low,mid);
         partisi(data,mid+1,high);
         mergesort(data,low,mid,high);
    }
}

void mergesort(int data[],int low,int mid,int high)
{
    int i,m,k,l,temp[max];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high))
 {

         if(data[l]<=data[m])
   {
             temp[i]=data[l];
             l++;
         }
         else
   {
             temp[i]=data[m];
             m++;
         }
         i++;
    }
    if(l>mid)
 {
         for(k=m;k<=high;k++)
   {
             temp[i]=data[k];
             i++;
         }
    }
    else
 {
         for(k=l;k<=mid;k++)
   {
             temp[i]=data[k];
             i++;
         }
    }
    for(k=low;k<=high;k++)
 {
         data[k]=temp[k];
    }

   
}

fungsi tampil

void tampil()
{
 int j;
 puts("\n");
 for(j=0;j<n;j++)
 {printf("%d\t",data[j]);}
 puts("\n");
}

Video penjelasan Merge Sorting