Program Merge Sort dengan Algoritma Divide & Conquer

     Merge sort dilakukan dengan menggunakan 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.

Contoh Algoritma/Pseudo Codenya Adalah :

procedure MergeSort(input/output A : TabelInt,   input i, j : integer)  { Mengurutkan tabel A[i..j] dengan algoritma    Merge Sort Masukan: Tabel A dengan n elemen   Keluaran: Tabel A yang terurut } Deklarasi:    k : integer Algoritma:    if i < j then  { Ukuran(A)> 1}      k¬(i+j) div 2      MergeSort(A, i, k)      MergeSort(A, k+1, j)      Merge(A, i, k, j)    endif procedure Merge(input/output A : TabelInt, input kiri, tengah,kanan : integer) { Menggabung tabel A[kiri..tengah] dan tabel    A[tengah+1..kanan]   menjadi tabel A[kiri..kanan] yang terurut menaik.   Masukan: A[kiri..tengah] dan tabel A[tengah+1..kanan]    yang sudah terurut menaik.   Keluaran: A[kiri..kanan] yang terurut menaik. } Deklarasi B : TabelInt i, kidal1, kidal2 : integer Algoritma: kidal1¬kiri { A[kiri .. tengah] } kidal2¬tengah + 1   { A[tengah+1 .. kanan] } i¬kiri while (kidal1 £ tengah) and (kidal2 £ kanan) do         if Akidal1 £ Akidal2 then         Bi¬Akidal1    kidal1¬kidal1 + 1     else         Bi¬Akidal2    kidal2¬kidal2 + 1    endif    i¬i + 1     endwhile  { kidal1 > tengah or kidal2 > kanan } { salin sisa A bagian kiri ke B, jika ada } while (kidal1 £ tengah) do         Bi¬Akidal1    kidal1¬kidal1 + 1    i¬i + 1     endwhile    { kidal1 > tengah }    { salin sisa A bagian kanan ke B, jika ada } while (kidal2 £ kanan) do     Bi¬Akidal2    kidal2¬kidal2 + 1    i¬i + 1 endwhile  { kidal2 > kanan }    { salin kembali elemen-elemen tabel B ke A } for i¬kiri to kanan do    Ai¬Bi     endfor       { diperoleh tabel A yang terurut membesar }

Untuk implementasinya ke Bahasa C++ Adalah :

#include <cstdlib>
#include <iostream>

using namespace std;

void Merge(int* A, int kiri,int tengah, int kanan){

 int B[kiri+kanan];
 int i,kidal1,kidal2;


 kidal1=kiri;
 kidal2=tengah+1;
 i=kiri;

 while (kidal1<=tengah && kidal2 <= kanan){
  if(A[kidal1] <= A[kidal2]){
   B[i]=A[kidal1];
   kidal1++;
  }
  else{
   B[i]=A[kidal2];
   kidal2++;
  }
  i++;
 }

    while ( kidal1 <= tengah ){
        B[i] = A[kidal1];
        kidal1++;
        i++;
        }

    while ( kidal2 <= kanan ){
        B[i] = A[kidal2];
        kidal2++;
        i++;
        }

 for (int i=kiri;i<= kanan;i++){
  A[i]=B[i];
 }
}

void MergeSort (int* A, int i, int j){
 int k;
 if (i<j){
  k= ((i+j)/2);
  MergeSort(A, i, k);
  MergeSort(A, k+1, j);
  Merge(A, i, k, j);
 }
}

int main(int argc, char *argv[])
{
 int n;
 int i;
 int j;

 cout<<"Masukkan junlah data : ";
 cin>>n;
 i=1;
 j=n;
 int A[n];

 for (int x=1;x<=n;x++){
  cout<<"masukan data ke-"<<x<<" : ";
  cin>>A[x];
 }
 cout<<"Data sebelum diurutkan : ";
 for (int x=1;x<=j;x++){
  cout<<A[x]<<" ";
    }
    cout<<endl;

 MergeSort(A,i,j);

 cout<<"Data sesudah diurutkan : ";
 for (int x=1;x<=j;x++){
  cout<<A[x]<<" ";
    }
    cout<<endl;

 system("pause");
 return 0;
}

Hasil Eksekusinya :