Recently, when I saw the fourth edition of “Algorithm”, I did the exercise in this section, and I felt some harvest, so I shared it with you, which is also to cast a brick to attract jade.

So before we merge sort, let’s ask ourselves, how do we merge two ordered arrays? For example, here are two arrays A and B, both of which are ordered

A: 2 and 4 b: 1 hc-positieCopy the code

How do I merge these two arrays? Since the array is ordered, we take full advantage of the orderability of the array, set two Pointers I,j, respectively to the first address of the array, and then compare the corresponding values of the Pointers A [I] and b[j], we always take the smaller value, into the final array. Because the two arrays are ordered, each time you put a smaller value into the final array, the final array will be ordered after the comparison.

Note that, regardless of the number and size of the two arrays, only one element can be used up at any given moment, not both. Why? Because according to the procedure above, the smallest array must be used up first. Even if two arrays have the same size and number of elements, only one array will run out first.

Let’s plot the process. At the beginning, I =0,j=0, they both point to the beginning of the array, and the smaller value is 1, so I take b[j] and put it in C, and then J goes to the next location.

A: 2 and 4 I b: 1 hc-positie j c: a: 2 and 4 I b: 1 hc-positie j c: 1Copy the code

At this point I =0,j=1, continue the comparison,2<3,2 put in c, I move to the next value

A :2,3,4 b:1,3,5,7 c:1,2Copy the code

At this point I = 1, j = 1, because a [I] = = a [j], so a [I] < b [j] fails, take out [j] into c, b j to move to the next value

A :2,3,4 b:1,3,5,7Copy the code

Now j is equal to 2, I is equal to 1, and we keep comparing, we put 3 in c, and we move I to the next value

A :2,3,4 b:1,3,5,7 c:1,2,3,3Copy the code

At this point,j=2, I =2, continue the comparison, put 4 in C, I =4, beyond the index range of A, indicating that the element A has been used up

A :2,3,4 b:1,3,5,7 c:1,2,3,3,4Copy the code

Since element A is used up, we only need to take out the remaining elements from B and put them into C, and the final C is as follows:

C :1,2,3,3, 5,7Copy the code

Convert the above procedure into code

public static int[] merge(int[] a,int[] b){ int len1=a.length; int len2=b.length; int len=len1+len2; int[] c=new int[len]; int i=0,j=0; for(int k=0; k<len; K++) {/ / a array elements are used up, in turn, the remaining elements in the c b if (I = = len1) c [k] [j++] = b; Else if(j==len2) c[k]=a[i++]; if(j==len2) c[k]=a[i++]; / / if the two arrays are useless over, take less in c else if (a [I] < b [j]) c = [k] a [i++]; else c[k]=b[j++]; } return c; }Copy the code

The above procedure is simple,merge method is merge. Simply pass two ordered arrays to merge, which returns an ordered sum array. The question comes, how to make a disorderly array into two orderly array, to ensure the normal operation of the merge?