#include <iostream>
using namespace std;
void Merge(int *c, int *d, int l, int m, int r){
//Merge c[l:m] amd c[m:r] to d[l:r]
int i =l; //cursor for first segment
int j = m+1; //cursor for second
int k = l; //cursor for result
//merge until i or j exits its segment
while((i<=m) && (j<=r)){
if(c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
}
//take care over left overs
if(i > m) for(int q =j; q<=r;q++) d[k++] = c[q];
else for (int q = i; q<=m; q++) d[k++] = c[q];
}
void MergePass(int *x, int *y, int s, int n){
//Merge adjacent segments of size s
int i = 0;
while(i <=n -1 * s){
//Merge two adjacent segment of size a
Merge(x,y,i,i+s-1,i+2*s-1);
i = i + 2 *s;
}
//fewer than 2s elements remain
if(i+s < n) Merge(x,y,i,i+s-1,n-1);
else for(int j =i; j<n; j++){
//Copy last segment to y
y[j]= x[j];
}
}
void MergeSort(int *a, int n){
//Sort a[0:n-1] using merge sort
int *b= new int[n];
int s = 1; //Segment Size
while(s<n){
MergePass(a, b, s, n); //merge from a to b
s += s;
MergePass(b,a,s,n); // merge from b to a
s += s;
}
}
int main(int argc, char **argv)
{
int a[6]={10,4,87,17,53,34};
MergeSort(a,6);
int i=0;
while(i<6){
cout<<"--"<<a[i++];
}
return 0;
}
courtesy : Data Structures, Algorithms and Applications in C++, SAHNI, McGrawHill
