Merging Example

Example : A Merging Example/program in C to show Merge Sort.

#include<stdio.h>
#include<conio.h>

void ArrOutput(int x[], int arrsize);
void mergeSort(int x[], int index1, int index2);
   
void merge(int x1[], int beg, int mid, int end);
int i;

int main()  
{  
    int m,arrsize;
    
		printf("Enter the size of array for Merge sort = ");
		scanf("%d",&m);
		int x[m];
		
		printf("\nNow, enter %d values for an array for Merge sort = \n",m);
		for(i=0;i<m;i++)
		{
		  scanf("%d",&x[i]);
		}		
    
		arrsize=m;
		
    printf("\nThe output of array elements before Merge sort are = \n");  
    ArrOutput(x, arrsize);		
		  
    mergeSort(x,0,arrsize-1);
		  
    printf("\nThe output of array elements after Merge sort are = \n");  
    ArrOutput(x,arrsize); 
		 
    return 0;  
}

/* A Function to display the output of the array */  
void ArrOutput(int x3[], int arrsize1)  
{  
  for(i=0;i<arrsize1;i++)
    {
	printf("%d\n",x3[i]);  		
    }        
} 

void mergeSort(int x1[], int beg, int end)  
{  
    if (beg<end)   
    {  
        int mid=(beg+end)/2;
				  
        mergeSort(x1,beg,mid);
				  
        mergeSort(x1,mid+1,end);
				  
        merge(x1, beg, mid, end);  
    }  
}    
  
// Function to merge the divided array(i.e. subarrays of x[])   
void merge(int x2[], int beg1, int mid1, int end1)    
{    
    int i,j,k;  
    int arrsize1=mid1-beg1+1;    
    int arrsize2=end1-mid1;    
      
    int LeftArray[arrsize1],RightArray[arrsize2]; //temporary arrays after split/divide 
      
    /* copy data to temporary arrays */  
    for (i=0; i<arrsize1; i++)    
      LeftArray[i]=x2[beg1+i];
		    
    for (j=0; j<arrsize2;j++)    
      RightArray[j]=x2[mid1+1+j];    
      
    i = 0; // initial index of first divide sub-array  
    j = 0; // initial index of second divide sub-array    
    k = beg1;  // initial index of merged two sub-arrays  
      
    while(i<arrsize1 && j<arrsize2)    
    {    
        if(LeftArray[i]<=RightArray[j])    
        {    
            x2[k]=LeftArray[i];    
            i++;    
        }    
        else    
        {    
            x2[k]=RightArray[j];    
            j++;    
        }    
        k++;    
    }
		    
    while(i<arrsize1)    
    {    
        x2[k]=LeftArray[i];    
        i++;    
        k++;    
    }    
      
    while(j<arrsize2)    
    {    
        x2[k]=RightArray[j];    
        j++;    
        k++;    
    }    
}

Output:
Enter the size of array for Merge sort = 3

Now, enter 3 values for an array for Merge sort =
200
1
50

The output of array elements before Merge sort are =
200
1
50

The output of array elements after Merge sort are =
1
50
200