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
Also check this:-
codechef problems:-
- Primary test
- Sum or difference
- point and line
Wipro :-
- Update the booking ID | Wipro previous year question paper solution
- Pages in PDF
- Find the location id
- Find the odd digits
- Find the Product ID
Infytq :-
Key Points;-
Hackerrank:-
- Python : missing characters : hackerrank solution
- Python : string transformation | Hackerrank solution
- Active Traders certification test problem | Hackerrank Solution
- Usernames changes certification test problem | Hackerrank Solution
- string Representation of objects certification test hackerrank solution
- Average Function | hackerrank certification problem solution
C-tutorial:-
- Micros in C
- Pointer in c
- Function declaration
- Types of user define function
- return type of function
- 2D array
See more:-
- c program to convert specified days into years weeks and days
- Print Reverse Hollow Pyramid
- Update the booking ID | Wipro previous year question paper
- Pages in PDF | Wipro previous year question paper
- Sparse Matrix in data structure
- Find the location ID | Wipro previous year Coding question
- find the odd digits | Wipro Coding question
- Find the product id | Wipro Coding question
- Difference between static and dynamic memory allocation
- What is asymptotic Notation