Algoritma Divide and Conquer : Merge Sort

Algoritma Divide and Conquer pada prinsipnya memecah-mecah masalah yang ada menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.

langkah-langkahnya:

• Divide: Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama). 
• Conquer: Memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif). 
• Combine: Menggabungkan solusi masing-masing masalah sehingga membentuk solusi masalah semula. ^[sumber]

salah satu contoh algoritma devide and conquer adalah merge sort

dan ini adalah implementasinya dalam c++


#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;
}

NB : diasumsikan array dimulai dari 1