# include <iostream.h>
 # include <conio.h>

 void merge(long [],int,int);
 void merge_sort(long [],int);


 main( )

    {
       clrscr( );

       constint array_size=10;

       long array[array_size]={0};

       cout<<"\n ******************************************************************************"<<endl;
       cout<<" *********************************  Merge Sort  *******************************"<<endl;
       cout<<" ******************************************************************************"<<endl;

       cout<<"\n * Array size = 10"<<endl;
       cout<<" * Data Type = long"<<endl;

       gotoxy(1,24);
       cout<<" ******************************************************************************";
       gotoxy(1,25);
       cout<<" ******************************************************************************";

       gotoxy(1,10);
       cout<<" Enter the array : "<<endl<<endl;

       for(int count_1=0;count_1<array_size;count_1++)
      {
         cout<<"\t Element["<<count_1<<"] = ";
         cin>>array[count_1];
      }

       merge_sort(array,array_size);

       gotoxy(40,10);
       cout<<" Sorted Array : ";

       for(int count_2=0;count_2<array_size;count_2++)
      {
         gotoxy(50,12+count_2);
         cout<<"Element["<<count_2<<"] = "<<array[count_2]<<endl;
      }

       getch( );
       return 0;

    }

 /*************************************************************************//*************************************************************************//***********************  Function Definitions  **************************//*************************************************************************//*************************************************************************//*************************************************************************///--------------------  mrege_sort(long [],int,int)  --------------------///*************************************************************************/void merge(long array[],int array_size_1,int array_size_2)
    {
       long *temp_array=newlong[array_size_1+array_size_2];

       int count_1=0;
       int count_2=0;
       int count_3=0;

       while(count_2<array_size_1 && count_3<array_size_2)
      {
          if(array[count_2]<=array[array_size_1+count_3])
         {
            temp_array[count_1]=array[count_2];
            count_2++;
         }

         else
        {
           temp_array[count_1]=array[array_size_1+count_3];
           count_3++;
        }
         count_1++;
      }

       while(count_2<array_size_1)
      {
         temp_array[count_1]=array[count_2];
         count_1++;
         count_2++;
      }

       while(count_3<array_size_2)
      {
         temp_array[count_1]=array[array_size_1+count_3];
         count_3++;
         count_1++;
      }

       for(int count_4=0;count_4<array_size_1+array_size_2;count_4++)
      array[count_4]=temp_array[count_4];

       delete temp_array;
    }

 /*************************************************************************///------------------------  merge_sort(int[],int)  ----------------------///*************************************************************************/void merge_sort(long array[],int array_size)
    {
       if(array_size>1)
      {
         int sub_array_size_1=array_size/2;
         int sub_array_size_2=array_size-sub_array_size_1;

         merge_sort(array,sub_array_size_1);
         merge_sort(array+sub_array_size_1,sub_array_size_2);
         merge(array,sub_array_size_1,sub_array_size_2);
      }
    }