what is Merge sort?
GIAN Tutorials
11:15 PM
Merge sort Merge sort is the algorithm which follows divide and conquer approach. Consider an array A of n number of elements. The algorithm processes the elements in 3 steps. If A Contains 0 or 1 elements then it is already sorted, otherwise, Divide A into two sub-array of equal number of elements. Conquer means sort the two sub-arrays recursively using the merge sort. Combine the sub-arrays to form a single final sorted array maintaining the ordering of the array. The main idea behind merge sort is that, the short list takes less time to be sorted. Complexity Complexity Best case Average Case Worst Case Time Complexity O(n log n) O(n log n) O(n log n) Space Complexity O(n) Example : Consider the following array of 7 elements. Sort the array by using merge sort. A = { 10 , 5 , 2 , 23 , 45 , 21 , 7 } Algorithm Step 1 : [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0 Step 2 : Repeat while (I <= MID) AND (J<=END) IF ARR[I] < ARR[J] SET
