Merge Sort Algorithm in Array

Merge Sort Algorithm

Merge Sort Algorithm

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[1], A[2], . . . ,A[r] and array B having m elements B[1], B[2], . . . , 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

Merge Sort Algorithm

Merge Sort Algorithm – 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.

Pass 1:

Compare A [1] with B [1]. That is compare 10 with 9.

Assign smaller value to C [1]. So 9 is assign to C [1].

Merge Sort Algorithm - Pass 1

Pass 1

Pass 2:

Now compare A [1] with B [2]. As A [1] < B [2], the value of A [1] is assigned to C [2]

Merge Sort Algorithm - Pass 2

Pass 2

This will continue till the end of either of the array.

Pass 3:

Merge Sort Algorithm - Pass 3

Pass 3

Pass 4:

Merge Sort Algorithm - Pass 4

Pass 4

 

Pass 5:

Merge Sort Algorithm - Pass 5

Pass 5

Pass 6:

Merge Sort Algorithm - Pass 6

Pass 6

Pass 7:

Merge Sort Algorithm - Pass 7

Pass 7

Pass 8:

Merge Sort Algorithm - Pass 8

Pass 8

Pass 9:

Merge Sort Algorithm - Pass 9

Pass 9

Pass 10:

Merge Sort Algorithm - Pass 10

Pass 10

Pass 11:

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.

Merge Sort Algorithm - Pass 11

Pass 11

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.

You may also like...

Leave a Reply

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