Merge Sort C++

Merge sort adalah metode pengurutan yang menggunakan pola divide and conquer. Strateginya adalah dengan membagi sekelompok data yang akan diurutkan menjadi beberapa kelompok kecil terdiri dari maksimal dua nilai untuk dibandingkan dan digabungkan lagi secara keseluruhan.

Langkah-langkah Kerja dalam Merge sort:

 1. Divide Memilah elemen – elemen dari rangkaian data menjadi dua bagian dan mengulangi pemilahan hingga satu elemen terdiri maksimal dua nilai.

 2. Conquer Mengurutkan masing-masing elemen

. 3. Kombinasi Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan. Proses.

Program :
#include <iostream>
#include <conio.h>
using namespace std;

int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
 int mid;
 if(low<high)
 {
  mid=(low+high)/2;
  merge_sort(low,mid);
  merge_sort(mid+1,high);
  merge(low,mid,high);
 }
}
void merge(int low,int mid,int high)
{
 int h,i,j,b[50],k;
 h=low;
 i=low;
 j=mid+1;
 while((h<=mid)&&(j<=high))
 {
  if(a[h]<=a[j])
  {
   b[i]=a[h]; h++;
  }
  else
  {
   b[i]=a[j]; j++;
  } i++;
 }
 if(h>mid)
 {
  for(k=j;k<=high;k++)
  {
   b[i]=a[k]; i++;
  }
 }
 else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k]; i++;
  }
 }
 for(k=low;k<=high;k++)
  a[k]=b[k];
}
main()
{
 int num,i;
 cout<<"---------------------------"<<endl;
 cout<<"    ALGORITMA MERGE SORT C++ "<<endl;
 cout<<"---------------------------"<<endl;
 cout<<endl;
 cout<<"Masukkan Banyak Bilangan: ";cin>>num;
 cout<<endl;
 cout<<"Sekarang masukkan "<< num <<" Bilangan yang ingin Diurutkan :"<<endl;
 for(i=1;i<=num;i++)
 {
  cout<<"Bilangan ke-"<<i<<" :";cin>>a[i] ;
 }
 merge_sort(1,num);
 cout<<endl;
 cout<<"Hasil akhir pengurutan :"<<endl;
 cout<<endl;
 for(i=1;i<=num;i++)
  cout<<a[i]<<" ";
 cout<<endl<<endl<<endl<<endl;
 }

Sumber :

[1] Fauzi, Indrayana, 2005. Pebandingan Kecepatan/Waktu Komputasi Beberapa Algortima Pengurutan (Sorting), Institut Teknologi Bandung. 

[2] Wisudawan, Wahyu Fahmy, 2007. Kompleksitas Algoritma Sorting yang Populer Dipakai. Bandung: Teknik Informatika, Institut Teknologi Bandung.

[3] Yahfizham, 2008. Analisis Waktu Algoritma Quick sort dan Merge sort.

 [4] Hendra Saptadi, Arief . 2013, Analisis Algoritma Insertion sort, Merge sort dan Implementasinya dalam Bahasa Pemograman C++. Akademi Teknik Telekomunikasi Shandy Putra Purwokerto