MergeSort

MergeSort adalah Metode pengurutan lanjut, sama dengan metode QuickSort. Metode ini juga menggunakan konsep devide and conquer yang membagi data S dalam dua kelompok yaitu S1 dan S2yang tidak beririsan (disjoint). Proses data dilakukan secara rekursif sampai data tidak dapat dibagi lagi atau dengan kata lain data dalam sub bagian menjadi tunggal.
Setelah data tidak dapat dibagi, proses penggabungan (Merging) dilakukan antara sub-sub bagian dengan memeperhatikan urutan data yang diinginkan (Ascending atau Descending). Proses penggabungan ini dilakukan sampai semua data tergabung dan terurut sesuai urutan yang diinginkan kompleksitas Algoritma MergeSort adalah O(n log n).

Penerapan Algoritma MergeSort: 

#include <iostream>
#include <cstdio>
using namespace std;
void cetak(int *array,int length) //print array elements
{
int i=0;
for(i=0;i<length;i++)
cout<<array[i] << ” ” ;
cout << endl;
}
void merge(int *arr, int size1, int size2) {
int temp[size1+size2];
int ptr1=0, ptr2=0;
int *arr1 = arr, *arr2 = arr+size1;
while (ptr1+ptr2 < size1+size2) {
if (ptr1 < size1 && arr1[ptr1] <= arr2[ptr2]
|| ptr1 < size1 && ptr2 >= size2)
temp[ptr1+ptr2] = arr1[ptr1++];
if (ptr2 < size2 && arr2[ptr2] < arr1[ptr1]
|| ptr2 < size2 && ptr1 >= size1)
temp[ptr1+ptr2] = arr2[ptr2++];
}
for (int i=0; i < size1+size2; i++)
arr[i] = temp[i];
}
void mergeSort(int *arr, int size) {
if (size == 1)
return;
int size1 = size/2, size2 = size-size1;
mergeSort(arr, size1);
mergeSort(arr+size1, size2);
merge(arr, size1, size2);
}
int main()
{
int a[]={9,6,5,23,2,66,14,8,2,7,1,8};   // array to sort
cetak(a,12);               // print elements
mergeSort(a,12);                 //call to bubble sort
cetak(a,12);               // print elements
return 0;
}