merge_sort.c

#include<stdio.h>

/*copy two arrays*/
void copyArray(int readFrom[], int begin, int end, int writeTo[])
{
	int i=0,j=begin;
	while(i<end-begin+1)
	{
		writeTo[i] = readFrom[j];
		i++;
		j++;
	}	
}

/* print array */
void printArray(int A[], int N)
{
	int i=0;
	for (i = 0; i < N; ++i)
	{
		printf("%d ",A[i]);
	}
}

/* merge two arrays*/
void mergeArrays(int A[], int iBegin, int iMiddle, int iEnd)
{
	/*
      array1 = A[iBegin - iMiddle]
      array2 = A[iMiddle+1 - iEnd]
      array1 and array2 are already sorted seperatley by the time this is called
      all we do here is merge them             
	  Typical variant requires additional two temporary arrays 
	*/    
    int leftSize = iMiddle - iBegin + 1;
    int rightSize = iEnd - iMiddle;
    int tempLeft[leftSize];
    int tempRight[rightSize];
    int i,leftCount=0,rightCount=0;
    /* copy A into temp arrays*/
    copyArray(A, iBegin, iMiddle, tempLeft);
    copyArray(A, iMiddle+1, iEnd, tempRight);
    
    /* merging */
    i = iBegin;
    while(leftCount < leftSize && rightCount < rightSize)
    {
    	if(tempLeft[leftCount] <= tempRight[rightCount])
    	{
    		A[i] = tempLeft[leftCount];
    		leftCount++;
    	}
    	else
    	{
    		A[i] = tempRight[rightCount];
    		rightCount++;
    	}
    	i++;    		
    }
    
    /*copying remaining elements of temp array if there are any*/
    while(leftCount < leftSize)
    {
    	A[i] = tempLeft[leftCount];
    	leftCount++;
    	i++;
    }
    
    while(rightCount < rightSize)
    {
    	A[i] = tempRight[rightCount];
    	rightCount++;
    	i++;
    }
}


/* splits recursivley and calls the merge function */
void mergeSort(int A[], int iBegin, int iEnd)
{
	/*
	recursivley split them until the run size is 1 i.e. 
	splitting stops when iEnd = iBegin + 1;
    then merges them and return back up the call chain    
	iBegin : Beginn index
	iEnd   : End index
	iMiddle: Middle index 
	*/
	int iMiddle;
	if(iEnd > iBegin)
	{
		iMiddle = (iEnd+iBegin)/2;
		mergeSort(A, iBegin, iMiddle);
		mergeSort(A, iMiddle+1 , iEnd);
		mergeArrays(A,iBegin,iMiddle,iEnd); 
	}
}


int main()
{
	int T,N;
	int A[200];
	int i;
	scanf("%d",&T);
	while(T>0)
	{
		scanf("%d",&N);
		for (i = 0; i < N; ++i)
			scanf("%d",&A[i]);
		mergeSort(A,0,N-1);
		printArray(A,N);
		printf("\n");
		--T;
	}
	return 0;

}