#include <iostream>
#include <stdlib.h>
using namespace std;
void Merge(int*arr,int start,int mid,int end)
{
int *temp=new int[end-start];
int sub1=start;
int sub2=mid;
int loc=0;
while( (sub1 < mid) && (sub2 < end) )
{
if(arr[sub2]<arr[sub1])
temp[loc++]=arr[sub2++];
else
temp[loc++]=arr[sub1++];
}
for(int i=sub1;i<mid;i++)
temp[loc++]=arr[sub1];
for(int i=sub2;i<end;i++)
temp[loc++]=arr[sub2];
for(int i=0;i<end-start;i++)
arr[start+i]=temp[i];
delete[] temp;
}
void Merge_sort(int *arr,int start,int end)
{
if(end-start<2)
return;
int mid= (start+end)/2;
Merge_sort(arr,start,mid);
Merge_sort(arr,mid,end);
Merge(arr,start,mid,end);
}
int main(int argc, char *argv[])
{
int a[10];
for(int i=0;i<10;i++)
{
a[i]=rand()%10;
cout<<a[i]<<endl;
}
Merge_sort(a,0,10);
cout<<"++++++++++++++++++++++\n";
for(int i=0;i<10;i++)
{
cout<<a[i]<<endl;
}
}