Merge Sort In C.

1)Merge sort is a sorting algorithm that uses the divide and conquer and combine algorithmic paradigm.

2)Divide means partitioning the n-element array to be sorted into two sub-arrays of n/2 elements.

3)If A is an array containing zero or one element, then it is already sorted. However, if there are more elements in the array, divide A into two sub-arrays, A1 and A2, each containing about half of the elements of A.

4)Conquer means merging the two sorted sub-arrays of size n/2 to produce the sorted array of n elements.

Merge sort algorithm focuses on two main concepts to improve its performance (running time): 1. A smaller list takes fewer steps and thus less time to sort than a large list. 2. As number of steps is relatively less, thus less time is needed to create a sorted list from two sorted lists rather than creating it using two unsorted lists.

Let's see C program for Merge Sorting.

#include<stdio.h>
#include<conio.h>
int main()
{
    int c[50],n,m;
    clrscr();
    printf("Enter size of array :- ");
    scanf("%d",&n);
    printf("Enter %d elements in Array :-\n",n);
    for(m=0; m<n; m++)
    {
        scanf("%d",&c[m]);
    }
    printf("Elements of Array after merge sort are:\n");
    merge_sort(c,0,n-1);
    for(m=0; m<n; m++)
    {
        printf("\n %d",c[m]);
    }
    return 0;
}
void merge(int a[50], int f, int mid, int l)
{
    int i=f,j=mid+1,k=f;
    int b[50];
    while( (i<=mid) && (j<=l))
    {
        if(a[i] <= a[j])
        {
            b[k] = a[i];
            i++;
        }
        else
        {
            b[k] = a[j];
            j++;
        }
        k++;
    }
    if(i>mid)
    {
        while(j<=l)
        {
            b[k]=a[j];
            j++;
            k++;
        }
    }
    else
    {
        while(i<=mid)
        {
            b[k]=a[i];
            i++;
            k++;
        }
    }
        for(k=f; k<=l; k++)
        {
            a[k]=b[k];
        }
}
void merge_sort(int a[50],int f,int l)
{
    int mid;
    if(f<l)
    {
        mid=(f+l)/2;
        merge_sort(a,f,mid);
        merge_sort(a,mid+1,l);
        merge(a,f,mid,l);
    }
}

    
    

 

*** Input ***

*** Output ***