MERGE SORT

/* merge sort*/

#include<stdio.h>

#define MAX 20

int a[MAX];

void merge(int low,int mid,int high)

{

    int temp[MAX];

    int i=low;

    int j=mid+1;

    int k=low;

    while((i<=mid)&&(j<=high))

    {

        if(a[i]<=a[j])

            temp[k++]=a[i++];

        else

            temp[k++]=a[j++];

    }

    while(i<=mid)

        temp[k++]=a[i++];

    while(j<=high)

        temp[k++]=a[j++];

    for(i=low;i<=high;i++)

        a[i]=temp[i];

}

void merge_sort(int low,int high)

{

    int mid;

    if(low!=high)

    {

        mid=(low+high)/2;

        merge_sort(low,mid);

        merge_sort(mid+1,high);

        merge(low,mid,high);

    }

}

main()

{

    int i,n;

    printf("\nEnter the number of elements:");

    scanf("%d",&n);

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

    {

        printf("\nEnter element %d:",i+1);

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

    }

    printf("\nUnsorted list is:\n ");

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

        printf("%d\t",a[i]);

    merge_sort(0,n-1);

    printf("\nSorted list is:\n");

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

        printf("%d\t",a[i]);

}

                             .......OUTPUT....

Enter the number of elements:5

Enter element 1:6

Enter element 2:3

Enter element 3:9

Enter element 4:4

Enter element 5:2

Unsorted list is:

 6      3       9       4       2

Sorted list is:

2       3       4       6       9