Merge Sort

 

Merge sort is a sorting algorithm in which we combine two sorted arrays into a single array.If suppose only one array is given.Then find the middle element and divide the array into two sub arrays and apply merge sort.

Algorithm : Merge sort has worst-case and average complexity both O(n log n), where n is the number of items being sorted.

Step 1 : Sort the two array using any sorting algorithm .

Step 2 : The first  element of first array is compared with the first element of second array.The smaller of the two is put in the resultant array.

Step 3 : The index of sub arrays is incremented  based on which which sub array’s element is put in the resultant array.In a similar way,the second,third till nth element are compared of both arrays and smaller element is put in the resultant array.

Complexity :

Algorithm Worst Case Average Case Best Case
Merge Sort O(n log n) O(n log n) O(n log n)

Question :
Given two arrays.Sort the elements of both the arrays and put  to a third array using merge sort technique ?

Solution :
The problem is solved in iterative way.

Program :

 
 


Leave a comment

Your email address will not be published. Required fields are marked *

20 + four =