Merge Sort Technique in Data Structure Using C

3.4 Merge Sort: Merging means combining two sorted lists into one sorted list. First condition is that two sorted lists are compared. The smaller of both the elements is then stored in the third array. The sorting is complete when all the elements from both the lists are proper placed in the third array. We can understand this concept with help of below figure: 0 1 2 3 4 5 8 9 11 15 4 7 10 13 16 x y 4 z 4 5 z 4 5 7 z 4 5 7 8 z 4 5 7 8 9 z 4 5 7 8 9 10 z 4 5 7 8 9 10 11 z 4 5 7 8 9 10 11 13 z 4 5 7 8 9 10 11 13 15 z 4 5 7 8 9 10 11 13 15 16 z Assumed that arrays x and y are sorted contain 5 elements each. Then merge sort algorithm works as follows: 1. The arrays x and y are sorted using any algorithm. 2. The 0th element from the x array 5, is compared with the 0th element of y array 4. Since 4 is smaller than 5, 4 is placed in the third z array. 3. Now 0th element from the first x array ,5 is compared with 1st element from the second y array 7. Since 5 is smaller than 7, 5 is placed in z third array. 4. Now 1st element from first x array 8, is compared with the 1st element from the second y array, 7.Since 7 is smaller than 8, 7 is placed in the third z array. 5. Now the 1st element from the first x array , 8, is compared with 2nd element from the second y array 10. Since 8 is smaller than 10, 8 placed in the z third array. 6. The same procedure is repeated till end of the both arrays and placed rest of the elements. Advantages of Merge sort are as follow: 1. It is faster sorting technique. 2. This sorting technique hand large list. Disadvantages of Merge sort are as follow: 1. In this sorting technique required twice memory comparing to other sorting techniques. 2. At least two sorted lists requirements to implementation for this sorting technique.