The previous section explained how to merge two ordered arrays into one ordered array. This is also the responsibility of merge. But our final requirement is to sort an unordered array, so how to split an unordered array into two ordered arrays is the focus of this article

Take the array a:2,3,4,1,3,5,7. No matter how you split it, you can’t split it into two ordered arrays at once. So that brings us to the core of merge sort: dynamic merge. What does that mean?

Actually simple, also the first we look at each element as a length of 1 subarray, so each subarray is natural and orderly, we put the two adjacent subarray passed to merge method, you will get a length of 2 orderly array, and then put the two adjacent to the length of the subarray to merge method for 2, will be of length An ordered array of 4, and so on, until the two subarrays are of length A. length/2, at which point merge is called again to obtain the final result. Merge sort dynamically calls merge to obtain a larger ordered subarray, and then continues to merge the two larger ordered subarrays until the final order is formed.

I guess you didn’t get it, so let’s go over the picture again

2, 3, 4, 1, 3, 5, 7Copy the code

Above is the original array. We keep dichotomizing the array until it contains only one element. This gives us a series of ordered subarrays of length 1, which sets the stage for merge

First decomposition:

2, 3, 4, 1, 3, 5, 7Copy the code

Second decomposition:

2, 3, 4, 1, 3, 5, 7Copy the code

Third decomposition:

2, 3, 4, 1, 3, 5, 7Copy the code

Now I can merge in pairs,

2, 3, 1, 4, 3, 5, 7Copy the code

Merge two and two again

1, 2, 3, 4, 3, 5, 7Copy the code

Merge two and two again

One, two, three, three, four, five, sevenCopy the code

How do you do this programmatically? If you can think of recursion at this point, then congratulations, the next thing is easy, it doesn’t matter, I didn’t either. Strictly speaking, the figure above is not an exact representation of the recursive process (but the principle is the same). In fact, I deliberately omitted to mix the recursive details with the above process in order to make it more concise.

I always thought recursion was a great invention, that it could represent complex processes in simple code

Before we recurse, let’s make a simple change to the merge method. The original merge method looks like this

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

Two arrays are represented by two parameters, which we change to the following form for better compatibility with recursive methods

Public static void merge(int[] a,int[] aux,int lo,int mid, int hi) {int I = lo,j = mid + 1; For (int k = lo; k<=hi ; k++){ aux[k] = a[k]; } // start merging for(int k = lo; k<= hi; k++){ if(i > mid) a[k] = aux[j++]; else if(j > hi) a[k] = aux[i++]; else if(aux[j]<aux[i]) a[k] = aux[j++]; else a[k] = aux[i++]; }}Copy the code

A represents the original unordered array, AUX represents the auxiliary array, LO represents the start index of the first ordered array,mid represents the end index of the first ordered array, and hi represents the end index of the second ordered array. What about the starting index of the second ordered array? Yes, it’s mid+1, which means we’re now using multiple indexes to represent two ordered subarrays

Why aux? For example, I want to merge the two subarrays below

a:2   3    1     4
  lo  mid  mid+1 hi
Copy the code

The first subarray runs from lo to mid, and the second subarray runs from mid+1 to Hi. If you do not copy the elements to aux, then when you merge, because a[mid+1] < a[lo] So the 2 of a[lo] will be overwritten by the 1 of a[mid+1]. Once overwritten, subsequent comparisons will never get the 2 again, so we copy the elements of A into AUX beforehand, which is what the first for loop did

The second for loop is simple, once the two ordered all the elements are copied to the subarray aux, we can use the aux elements to compare, every time I put a smaller value in the a, because the array is a reference type, inside the method of array elements change, will effect to the outside of the method, so we don’t like the first merge method returns an array.

According to the above analysis and the properties of the recursive method, once the merge array of length 1 is merged, it automatically returns to the recursive state of length 2, and then returns layer by layer until the merge subarray of length A. length/2 is merged.

To help you understand the above, I’ve plotted the process recursively this time:

Initial disorder:

2, 3, 4, 1, 3, 5, 7Copy the code

Divide array two into left and right subarrays

2, 3, 4, 1, 3, 5, 7Copy the code

Because we’re recursing, we’re recursing the left subarray 2, 3, 4, 1, and the right subarray is still 3, 5, 7

2, 3, 4, 1, 3, 5, 7Copy the code

Similarly, we keep recursing the left subarray 2, 3, and the right subarray 4, 1

2, 3, 4, 1, 3, 5, 7Copy the code

Since the subarray length is 1, merge 2 and 3 subarrays, and return to the previous recursive state automatically.

2, 3, 4, 1, 3, 5, 7Copy the code

Now the left subarray is merged and the right subarray is recursed to 4, 1

2, 3, 4, 1, 3, 5, 7Copy the code

The length of the subarray is 1. Merge the subarray to form 1

2, 3, 1, 4, 3, 5, 7Copy the code

Merge the subarrays 2, 3, and 1, 4, and return to the previous state.

1, 2, 3, 4, 3, 5, 7Copy the code

Now the left subarray 1, 2, 3, 4 is sorted, and we recurse to the right subarray 3, 5, and 7

1, 2, 3, 4, 3, 5, 7Copy the code

Keep recursing to the left subarray 3, 5

1, 2, 3, 4, 3, 5, 7Copy the code

Subarray of length 1 begins merging

1, 2, 3, 4, 3, 5, 7Copy the code

We merge the left subarray 3, 5, because the right subarray only has 7, so we just return, and we merge the 3, 5, and 7 subarrays

1, 2, 3, 4, 3, 5, 7Copy the code

At this point, the left and right subarrays recurse, continue to merge, and get the final result

One, two, three, three, four, five, sevenCopy the code

The above process may seem complicated, but the corresponding recursive code is simple:

private void sort(int[] a,int[] aux,int lo,int hi){ if(hi <= lo) return; int mid = lo+(hi-lo)/2; Sort (a,aux,lo,mid); Sort (a,aux,mid+1,hi); // Merge two ordered arrays (a,aux,lo,mid,hi); }Copy the code

Plus our entry function, and we’re done

  public void sort(int[] a){
    aux = new int[a.length];
    sort(a,aux,0,a.length-1);
  }
Copy the code

Conclusion:

According to the above analysis, we use dichotomy to decompose the original unordered array step by step until the length of the subarray is 1, at which point we start merging. When you merge, you merge the two subarrays into one large subarray, and then you return to the previous recursive state, where lo and HI are exactly where they were before the decomposition, and then you continue merging until it’s finally sorted.

I did it by splitting the array in pairs and merging it, so that’s double merge. In theory, we could split three by three, and then merge three subarrays at a time, so that’s triple merge. And of course we can do k-way merge. When you encounter specific problems, you can use the test to determine the appropriate k value for optimal performance.