The Merge sort algorithm is based on divide and conquers strategy. First, the sequence to be sorted is decomposed into two halves ( Divide ). Each half is sorted independently ( Conquer ). Then the two sorted halves are merged to a sorted sequence ( Combine ).
The following procedure merge sort sorts a sequence a from index min to index max.
void merge(int ,int ,int ,int );
void part(int ,int ,int );
printf("\n\t------- Merge sorting method -------\n\n");
printf("Enter total no. of elements : ");
for(i=0; i<size; i++)
printf("Enter %d element : ",i+1);
printf("\n\t------- Merge sorted elements -------\n\n");
for(i=0; i<size; i++)
void part(int arr,int min,int max)
First, index m in the middle between lo and hi is determined. Then the first part of the sequence (from lo to m) and the second part (from m+1 to hi) are sorted by recursive calls of merge sort. Then the two sorted halves are merged by procedure merge. Recursion ends when lo = hi, i.e. when a subsequence consists of only one element.
The main work of the Merge sort algorithm is performed by function merge. There are different possibilities to implement this function.
The Merge method defined as follows,
void merge(int arr,int min,int mid,int max)
for(i=min; j<=mid && m<=max ; i++)
for(k=m; k<=max; k++)
for(k=j; k<=mid; k++)
for(k=min; k<=max; k++)
This variant of function merge requires in each case exactly the same number of steps –no matter if the input sequence is random, sorted or sorted in opposite direction.
Just like the above steps the second recursion will sort the sequence at the right hand side. Finally the both partitioned sorted sub arrays are get merged in the sorted sequence.
The final merging steps are as follows,
14 and 6 are compared and 6 placed in the first position.
Next comparison will be
Now comparing 14 and 33 14 is least value so place it in the second place. Next comparison,
Likewise the comparisons done till reaches the end of the sub arrays and the list will be sorted at last, the sorted list will be as follows,
The straightforward version of function merge requires at most 2n steps (n steps for copying the sequence to the intermediate array b, and at most n steps for copying it back to array a). The time complexity of merge sort is therefore
T(n) < = 2n + 2 T(n/2) And
T(1) = 0
The solution of this recursion yields
T(n) < = 2n log(n) include O(n log(n))
Thus, the merge sort algorithm is optimal, since the lower bound for the sorting problem of Ω (n log (n)) is attained.
In the more efficient variant, function merge requires at most 1.5n steps (n/2 steps for copying the first half of the sequence to the intermediate array b, n/2 steps for copying it back to array a, and at most n/2 steps for processing the second half). These yields a running time of merge sort of at most 1.5n log (n) steps.
Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.