Merge Sort Algorithm in Array
Merge Sort Algorithm in Array is a part of Learning Data Structure Series. In the last article of Selection Sort Algorithm in Array we learnt to sort the element in increasing order in which smallest element is placed to its correct location first.
Merge sort algorithm sorts the array using divide-n-conquer method. Suppose we have two array A and B. Both array are already sorted. Now we want to create another array having elements of both A and B in such a way that resulting array C should be sorted. In such cases we use Merge sort algorithm.
Merge Sort Algorithm
Let us consider an array A having n elements A, A, . . . ,A[r] and array B having m elements B, B, . . . , B[s]. Both the array has elements in increasing order. To merge these arrays in one, we make use of merge sort.
Let us first analyze the algorithm
MERGING ( A, R, B, S, C)
1. Set NA :=1 , NB := 1 and PTR :=1 2. Repeat while NA ≤ R and NB ≤ S If A [NA] < B [NB] then a) Set C [PTR] := A [NA] b) Set PTR := PTR +1 and NA := NA+1 Else a) Set C [PTR] := B [NB] b) Set PTR :=PTR+1 and NB :=NB+1 [End of If] [End of loop] 3. If NA > R then: Repeat for K = 0,1,2,3,...., S - NB Set C [PTR + K] := B [NB+K] [End of loop] Else Repeat for K = 0,1,2,3,...., R - NA Set C [PTR + K] := A [NA+K] [End of loop] [End of If] 5. Exit
In above algorithm, we have two arrays A and B having R and S elements, respectively. Here NA and NB are the index variables of array A and B. C is the resulting sorted array and it will have N=R+S elements. PTR is the index variable for C.
Let us learn it with example
In Merge Sort Algorithm, it is not compulsory that array A and B should have same number of elements. As both the arrays are already sorted, we just append remaining elements of bigger array to C.
Compare A  with B . That is compare 10 with 9.
Assign smaller value to C . So 9 is assign to C .
Now compare A  with B . As A  < B , the value of A  is assigned to C 
This will continue till the end of either of the array.
Now all the elements of array B has been shifted to C. Still array A has 3 more elements. Observe that, remaining three elements of A are already in sorted manner. So we can directly shift it to C without any comparison.
In this way Merge Sort Algorithm merges two sorted array to make one resulting sorted array.
Complexity of Merge Sort Algorithm
We compare each element of A with B and assign the smaller value to C. So the maximum no of comparisons required will be n =r + s. (where r and s are the number of elements of A and B). Accordingly the f(n) should not exceed n. So f(n) ≤ n
This brings us to the end of learning Array Data Structure and its operations like Insert, Delete, Search and Sort.
Learning Data Structure Series continues with Linked List Data Structure.