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

Insertion Sort

Merge Sort

Bubble Sort

Selection Sort

Quick Sort

C Program For Bubble Sort | C Programming

C Program For Selection Sort | C Programming

C Program For Quick Sort | C Programming

C Program For Merge Sort | C Programming

C Program for Insertion Sort | C Programming