Merge Sort is one of the sorting techniques in the data structure.
It is a simple technique to sort the element.
Merge is also used for sorting two individual unsorted lists to the sorted list.
It merges the list. and we will see Merge sort program in c with explanation.
Merge sort technique
In this technique we have an N number of an unsorted list in this, We divide each element into a separate partition.
First, We divide the whole list into two arrays then that two arrays are divided separately and sort each element after that we merge the partitioned set to one single array. Finally, We will get our sorted array by merge sort technique.
Merge Sort Algorithm
- Take a set of number an array.
- Divide the array into equal parts.
- Consider these two parts separately
- Now, Take the first part and partition the number until we have only one element left then start combining each number by comparing and arrange in order.
- For the second part also, Partition 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.
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 the 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.
Merge sort program in c
void mergesort(int a,int i,int j);
void merge(int a,int i1,int j1,int i2,int j2);
printf("Enter no of elements:");
printf("Enter array elements:");
printf("\nSorted array is :");
void mergesort(int a,int i,int j)
mergesort(a,i,mid); //left recursion
mergesort(a,mid+1,j); //right recursion
merge(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; //array used for merging
i=i1; //beginning of the first list
j=i2; //beginning of the second list
while(i<=j1 && j<=j2) //while elements in both lists
while(i<=j1) //copy remaining elements of the first list
while(j<=j2) //copy remaining elements of the second list
//Transfer elements from temp back to a
Enter number of elements:
Enter array elements
10 2 30 4 1
Sorted array is: 1 2 4 10 30