//Merge Sort with 2 segment
#include <conio.h>
#include <iostream.h>
#include <math.h>
int s[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
    int mid;
    if(low>=high) return;
    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 k,i,j,u[50],g;
    k=low;
    i=low;
    j=mid+1;
    while((i<=mid)&&(j<=high))
    {
        if(s[i]<s[j])
        {
            u[k++]=s[i++];
        }
        else
        {
            u[k++]=s[j++];
        }
    }
    if(i<=mid)
        for(g=k;g<=high;g++,i++) u[g]=s[i];
    else
        for(g=k;g<=high;g++,j++) u[g]=s[j];
    for(g=low;g<=high;g++) s[g]=u[g];
}

//*******************************
main()
{
    int num,g;
    cout<<"********************************************************************************"<<endl;
    cout<<"                             MERGE SORT PROGRAM"<<endl;
    cout<<"********************************************************************************"<<endl;
    cout<<endl<<endl;
    cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN PRESS ENTER]:"<<endl;
    cin>>num;
    cout<<endl;
    cout<<"Now, Please Enter the ( "<< num <<" ) numbers (ELEMENTS) [THEN PRESS ENTER]:"<<endl;
    for(g=1;g<=num;g++)
        cin>>s[g] ;
    merge_sort(1,num);
    cout<<endl;
    cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl;
    cout<<endl<<endl;
    for(g=1;g<=num;g++)
        cout<<s[g]<<"	";
    cout<<endl<<endl<<endl<<endl;
    getch();
}