Implementation of Merge Sort

AIM:

          To write a C program to implement Merge sort

ALGORITHM:

            Step 1: Start the program.

Step 2: To sort A[p .. r]: Divide Step: If a given array A has zero or one element,

simply return; it is already sorted. Otherwise, split A[p .. r] into two

sub arrays A[p .. q] and A[q + 1 .. r], each containing about half of the

elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

Step 3: Conquer Step: Conquer by recursively sorting the two sub arrays A[p .. q]

            and A[q + 1 .. r].

Step 4: Combine Step : Combine the elements back in A[p .. r] by merging the

            two sorted sub arrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To

            accomplish this step, we will define a procedure MERGE (A, p, q, r).

Step 5: Stop the program.

PROGRAM

#include<stdio.h>

#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);

void partition(int arr[],int low,int high);

int main()

{

int merge[MAX],i,n;

printf("Enter the total number of elements: ");

scanf("%d",&n);

printf("Enter the elements which to be sort: ");

for(i=0;i<n;i++)

{

scanf("%d",&merge[i]);

}

partition(merge,0,n-1);

printf("After merge sorting elements are: ");

for(i=0;i<n;i++)

{

printf("%d ",merge[i]);

}

return 0;

}

void partition(int arr[],int low,int high){

int mid;

if(low<high)

{

mid=(low+high)/2;

partition(arr,low,mid);

partition(arr,mid+1,high);

mergeSort(arr,low,mid,high);

}

}