Sort the elements of an array A in ascending order.

Condition Merge 2 arrays (each of 1 element)

Divide the non sorted array until the condition is verified and sort the divided parts into pairs.

Precisely:

• Recursively divide the non sorted array into 2 sub arrays
• Recursively sort each sub array
• Merge the 2 sub arrays

#include<stdio.h>
#include<conio.h>
#define SIZE 50


void Fusion(int T[], int lower, int upper, int middle)
{
	int i=lower , j= middle+1, k=0, c[upper-lower+1];
	while(i<=middle && j<=upper)
		if(T[i]<T[j])
			c[k++]=T[i++];
		else
			c[k++]=T[j++];
	// copy remaining elements into c
	while(i<=middle) 
		c[k++]=T[i++];
	while(j<=upper) 
		c[k++]=T[j++];

	// copy elements back to T
	for(i=lower,j=0;j<k;i++,j++) 
		T[i]=c[j];
}



void MergeSort(int T[], int lower, int upper)
{
	int middle;
	if(lower<upper)
	{
		middle=(lower+upper)/2;
		MergeSort(T,lower,middle);
		MergeSort(T,middle+1,upper);
		Fusion(T,lower,upper,middle);
	}
}

void main()
{
	int A[SIZE], N;
	int i, j, v;

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);

	for (i = 0; i < N; i++)
	{
		printf("Enter A[%d]: ", i);
		scanf("%d", &A[i]);
	}

 	/* Merge Sort  */
	MergeSort(A, 0, N-1);

	printf("\n\n** After sorting ** \n");
	for (i = 0; i < N; i++)
	{
		printf("A[%d]=%d\n", i, A[i]);
	}

	getch();
}