Program to illustrate the Merge Sort

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

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


 main( )

    {
       clrscr( );

       const int 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=new long[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);
      }
    }