Merge Sort is a one of the sorting techniques in data structure.
It is a simple technique to sort the element.
Merge is also used for sorting two individual unsorted list to sorted list.
It merge the list.
Merge sort technique
In this technique we have a N number of unsorted list in this, We divide each element into a separate partition.
First, We divide the whole list into two array then that two array are divided separately and sort the each element after that we merge the partitioned set to one single array. Finally, We will get our sorted array by merge sort technique.
Algorithm
- Take a set of number an array.
- Divide the array into equal parts.
- Consider these two parts separately
- Now, Take first part and partition the number until we have only one element left then start combining the each number by comparing and arrange in order.
- For second part also, Partition the each number until one number left then start combining each number by comparing and arranging in order.
- After this, Compare the two sorted array and arrange into a one sorted list.
- Finish
Example:-
Output :-
Sorted list – 3 9 10 27 38 43 82
In this way we will get the sorted list.
The passes or steps required for implementing merge Sort is N -1.
The time complexity for merge Sort is O(n log n) for worst case.
Advantages of merge sort
- It is very simple and easy sorting technique.
- Works very good for large data.
Disadvantage of merge sort
- This technique requires extra space for implementation.
- It is less efficient.
Program
| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 | #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 recursionmergesort(a,mid+1,j); //right recursionmerge(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 mergingint i,j,k;i=i1; //beginning of the first listj=i2; //beginning of the second listk=0;while(i<=j1 && j<=j2) //while elements in both lists{if(a[i]<a[j])temp[k++]=a[i++];elsetemp[k++]=a[j++];}while(i<=j1) //copy remaining elements of the first listtemp[k++]=a[i++];while(j<=j2) //copy remaining elements of the second listtemp[k++]=a[j++];//Transfer elements from temp[] back to a[]for(i=i1,j=0;i<=j2;i++,j++)a[i]=temp[j];} |
Output of program:
Enter number of elements:
5
Enter array elements
10 2 30 4 1
Sorted array is: 1 2 4 10 30