#include <iostream>
using namespace std;
int a[]={40,10,86,44,93,26,69,17};
void mergeSort(int begin,int end);
void merge(int begin,int mid,int mid1,int end);
int main() {
int left = 0; int right = 7;
mergeSort(left,right);
for(int i=0;i<8;i++)
cout<<a[i]<<"\t";
return 0;
}
void mergeSort(int begin,int end)
{
int mid;
while(begin<end)
{
mid = (begin+end)/2;
mergeSort(begin,mid);
mergeSort(mid+1,end);
merge(begin,mid,mid+1,end);
}
}
void merge(int begin,int mid,int mid1,int end)
{
int first = begin;
int second = mid1;
int k = 0;
int temp[8];
while(first <= mid && second<=end)
{
if(a[first]<a[second])
{
temp[k] = a[first];
first++;
k++;
}
else if(a[first]>a[second])
{
temp[k] = a[second];
second++;
k++;
}
else
{
temp[k] = a[second];
k++;
temp[k] = a[first];
k++;
first++;second++;
}
}
while(first<=mid)
{
temp[k] = a[first];
first++;
k++;
}
while(second<=end)
{
temp[k] = a[second];
second++;
k++;
}
for(int beg=begin, end=0 ; beg<=end ; beg++, end++)
{
a[beg] = temp[end] ;
}
}
