Program of Mergesort

What is Mergesort:-

Mergesort is an efficient  sorting algorithm which work on Divide and Conquer method like Quicksort. In this algorithm  we continuously divide the input array in two halves until each have only one element and then merge them in sorted order.

 

 

Time complexity of the mergesort:-

Time complexity of the mergesort in all three cases is O(nlogn).

Best Case: O(nlogn)

Avg Case: O(nlogn)

Worst Case: O(nlogn)

Recurrence Relation of the Mergesort: –

  T(n)= 2T(n/2)+Θ(n)

 

Program of Mergesort in C:-

#include<stdio.h>


// function of Megre the array 
void Merge(int a[],int l,int mid , int r)
{
    int i,j,k;
    i=l;
    j=mid+1;
    k=0;
    int b[r-l+1];
    while(i<=mid && j<=r)
    {
        if(a[i]>a[j])
          b[k++]=a[j++];
        else
         b[k++]=a[i++];
    }
    if(i<=mid)
    {
        while(i<=mid)
        {
            b[k++]=a[i++];
        }
    }
    else if(j<=r)
    {
        while(j<=r)
          b[k++]=a[j++];
    }
    
    // copying the element of the tem into original array 
    for(int i=0;i<k;i++)
    {
        a[i+l]=b[i];
    }
}
// funtion of MergeSort
void MergeSort(int a[], int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        MergeSort(a,l,mid);
        MergeSort(a,mid+1,r);
        Merge(a,l,mid,r);
    }
}


int main()
{
    int n;
    printf("Enter the lenght of the arary\n");
    scanf("%d",&n);
    int a[n];
    printf("Enter the element of the array\n");
    for(int i=0;i<n;i++)
    {
       scanf("%d",&a[i]);   
    }
   
    MergeSort(a,0,4);
    printf("Sorted arary is : \n");
    for(int i=0;i<5;i++)
      printf("%d ",a[i]);
    return 0;
}

Output:-

Enter the lenght of the arary
5
Enter the element of the array
1 3 2 4 3
Sorted arary is : 
1 2 3 3 4

 

Program of Mergesort in java:-

import java.util.*;
public class Main
{
    
    // function for mergersort
    
    static void MergeSort(int arr[], int l, int r)
    {
        if(l<r)
        {
            int mid = (l+r)/2;
            MergeSort(arr, l, mid);
            MergeSort(arr, mid+1, r);
            Merge(arr, l, mid, r);
        }
    }
    
    // fucntion for merging
    static void Merge(int arr[], int l, int mid, int r)
    {
        int i=l;
        int j=mid+1;
        int k=0;
        int B[] = new int[r-l+1];
        while(i<=mid && j<=r)
        {
            if(arr[i]<arr[j])
            {
                B[k++] = arr[i++]; 
            }
            else{
                B[k++] = arr[j++];
            }
        }
        if(i>mid)
        {
            while(j<=r)
            {
                B[k++]= arr[j++];
            }
        }
        else{
            while(i<=mid)
            {
                B[k++] = arr[i++];
            }
        }
        
        
        // fucntion for copying the element of temporary array into 
        // main array
        for(i=0; i<k; i++)
        {
            arr[i+l] = B[i];
        }
    }
    
    
    // function for priting the elelment of the array 
    static void PrintArray(int arr[])
    {
        System.out.println("Sorted array is :");
        for(int i=0; i<arr.length; i++)
        {
            System.out.print(arr[i]+" ");
        }
    }
    
    
    // Driver function
    public static void main(String[] args) {
        
        System.out.println("Enter the size of the array");
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        System.out.println("Enter the element of the array");
        for(int i=0; i<n; i++)
        {
            arr[i] = sc.nextInt();
        }
        
        // function calling
        MergeSort(arr, 0 , n-1);
        PrintArray(arr);
    }
}

 

Output:-

Enter the size of the array
5
Enter the element of the array
1 3 2 4 3
Sorted array is :
1 2 3 3 4