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```