Merge Sort

Merge Sort

• Merging is the process of combining two or more sorted files into a third sorted file.
• Procedure: In merge sort, we divide the file into n subfiles of size 1 and then merge adjacent pair of files. We then have n/2 files of size 2. We repeat this process until there is only one file remaining of size n.

Efficiency of Merge Sort

• Let us assume that the file size n is a power of 2, say n=2^m. Thus m=log₂n.
• It is therefore obvious that there are no more than m or log₂n passes in merge sort (since each pass divides the file into two parts), with each pass involving at most n comparisons.
• Thus, total number of comparisons in merge sort is at most = n*m = n*log₂n.
• Hence the time complexity of merge sort = O (n Iog n).
• Average case complexity = Worst case complexity = Best case complexity = O(n log n).

C Program For Merge Sort

#include<stdio.h>

void mergesort(int a[],int i,int j);

void merge(int a[],int i1,int j1,int i2,int j2);

int main()

{

    int a[30],n,i;

    printf("Enter no of elements:");

    scanf("%d",&n);

    printf("Enter array elements:");  

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

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

    mergesort(a,0,n-1);

    printf("\nSorted array is :");

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

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

    return 0;
}

void mergesort(int a[],int i,int j)

{
    int mid;        

    if(i<j)

    {

        mid=(i+j)/2;

        mergesort(a,i,mid);        //left

        mergesort(a,mid+1,j);    //right

        merge(a,i,mid,mid+1,j);    //merging of two sorted sub-arrays

    }

}

void merge(int a[],int i1,int j1,int i2,int j2)

{

    int temp[50];    //array used for merging

    int i,j,k;

    i=i1;    //beginning of the first list

    j=i2;    //beginning of the second list

    k=0;

    while(i<=j1 && j<=j2)    //while elements in both lists

    {

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

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

        else

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

    }   

    while(i<=j1)    //copy remaining elements of the first list

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

    while(j<=j2)    //copy remaining elements of the second list

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

    //Transfer elements from temp[] back to a[]

    for(i=i1,j=0;i<=j2;i++,j++)

        a[i]=temp[j];

}

Related Posts

Bubble Sort

Insertion Sort

Selection Sort

Quick Sort

C Program For Selection Sort | C Programming

C Program For Quick Sort | C Programming

C Program For Merge Sort | C Programming

C Program For Bubble Sort | C Programming

C Program for Insertion Sort | C Programming