Hashtag: “We are all little frogs” public account article

A lot of you, including kids, have felt or are feeling that implementing an algorithm in code is like doing a brain u-turn — it’s so easy when you look at the answer, but you just can’t write it.

What went wrong? This article starts with a very simple, but very important algorithm idea called merge sort, and takes a completely trivial view of what pitfalls we might encounter when implementing this algorithm, and how to solve them.

What is merge sort?

In case some of you don’t know what merge sort is, let’s introduce it.

Merge sort is a very classic sorting algorithm, this algorithm is very simple, a sentence can be described: a sorted array into two subarrays, the first two subarrays are sorted, and then the two sorted subarrays into a large sorted array.

There are three details hidden in the simple description:

  • Divide an array into two subarrays

  • Detail 2: Conquer: How to sort two subarrays?

  • Detail 3: Subproblem Combine: How to Combine two ordered subarrays into one large ordered array?

Let’s take a look at the above three details.

Detail 1

Splitting an array into two subarrays is very easy. We just need to calculate the index of the middle element. Then we can specify:

  • The elements from the beginning to the middle belong to a subarray

  • We start with the last element in the middle element, and we end up with the last element in another subarray

The index of the middle element = (index of the beginning element + index of the end element) / 2Copy the code

Tip: please consider here why don’t we use an array of elements contained in the number of divided by 2 way to calculate the middle element subscript, if calculated in this way the middle element subscript what happens (hint: can according to the amount contained in the array is singular or dual to separate discussion).

Details of the 2

Detail 2 is actually easy to solve. When sorting a subarray, you can divide the subarray into two subarrays, sort the two subarrays first, and then sort the two sorted subarrays, and then sort the subarray.

How to arrange subarrays? Let’s keep breaking it into two smaller arrays. Here we successfully enter nesting doll mode, until some child child… There’s only one element in the subarray and you don’t have to tear it apart.

That is, we can continue to break the subproblem into multiple subproblems, and then go into nesting mode until a subproblem is simple enough (in this case, until the subarray contains only one element).

Of course, the above description is not very intuitive, so let’s take a concrete example.

We have an unordered array [2, 7, 1, 4, 6, 5, 0, 4] :

This array contains eight elements and we split it into two groups: group 1 and group 2, each containing four elements:

The array of 4 elements is still too long, continue to split groups 1 and 2 into 2 groups, and now you have 4 groups: group 1.1, group 1.2, group 2.1, group 2.2, each containing 2 elements:

Continuing to split the 2-element array, we get 8 groups: 1.1.1 group, 1.1.2 group, 1.2.1 group, 1.2.2 group, 2.1.1 group, 2.1.2 group, 2.2.1 group, 2.2.2 group, each group contains only 1 element:

Now that each group contains only one element and cannot be split, you can sort the elements in the group. Obviously, an array with only one element is already sorted. That is, groups 1.1.1, 1.1.2, 1.2.1, 1.2.2, 2.1.1, 2.1.2, 2.2.1, 2.2.2 are sorted and do not need to be sorted.

Details of the 3

Detail 3 is also easy to solve by simply iterating through the two subarrays from the beginning, adding the smaller element of each subarray to the final result.

Let’s say we have two sorted arrays [2, 7] and [1, 4] containing two elements, and we want to merge the two arrays into one large ordered array, then we can define two variables I and j:

  • I is the subscript of the first subarray, starting at the beginning of the first subarray.

  • J represents the subscript of the second subarray, initially pointing to the beginning element of the second subarray.

As shown below:

We can then fill the final array with elements:

  • Step 1: Currently I points to element 2 and j points to element 1, compareiandjWhich element is smaller? Since 2>1, fill the element 1 pointed to by j into the result array and increment j by 1, as shown in the figure below:

  • Step 2: Currently I points to element 2 and j points to element 4, compareiandjWhich element is smaller? Since 2<4, fill the element 2 to which I points into the result array and increment I by 1, as shown in the picture below:

  • Step 3: Currently I points to element 7 and j points to element 4, compareiandjWhich element is smaller? Since 7>4, fill the element 4 pointed to by j into the result array and increment j by 1, as shown in the picture below:

  • Step 4: Currently, the element I points to is 7, and the element in the second subarray has been iterated over, so we can directly iterate over the first subarray. Fill the element 7 pointed to by I into the storage cabinet of the result array, and increment I by 1. The effect is as shown in the picture below:

Now that we know how to merge two ordered arrays into one large ordered array, we are ready to merge our subproblems.

Continuing with the example introduced when dealing with detail 2: Group 1.1.1, Group 1.1.2, Group 1.2.1, Group 1.2.2, Group 2.1.1, Group 2.1.2, Group 2.2.1, group 2.2.2 contains only 1 element, which means that the subproblem has been solved and now needs to be merged:

  • Merge the ordered arrays in 1.1.1 group and 1.1.2 group, and make 1.1 into an ordered array;

  • Merge the ordered arrays in 1.2.1 group and 1.2.2 group, and make 1.2 form an ordered array;

  • Merge the ordered arrays in 2.1.1 group and 2.1.2 group to form 2.1 into an ordered array;

  • Merge the ordered arrays in 2.2.1 group and 2.2.2 group to form 2.2 into an ordered array;

As shown below:

Tip: We colored the 2.1 group to indicate that the order of elements in the group has been rearranged.

Now groups 1.1, 1.2, 2.1, and 2.2 are four ordered arrays respectively, and can continue to merge subproblems:

  • Merge the ordered arrays in group 1.1 and group 1.2, and make 1 form an ordered array;

  • Merge the ordered arrays in group 2.1 and group 2.2 to form 2 into an ordered array.

As shown below:

Now that groups 1 and 2 are two ordered arrays respectively, we can continue merging subproblems:

  • will1 set ofandThe 2 groupsMerges an ordered array into an ordered array. As shown below:

At this point, the original problem of sorting an array of eight elements in the first place is solved!

Ok, so the flow of the algorithm is described. I believe that most of the small partners can easily understand the above merge sort algorithm process, it can also be well understood, but once the implementation of the pen, there is a snack more and less force to catch the foot, the following will analyze what is the problem we ~

Talk is cheap, show me the code

The language in which the algorithm is implemented is not important, but let’s use Java as an example to see how to write code to implement merge sort.

The mergeSort function is used to sort an int array of integers. The mergeSort function is used to sort an int array of integers.

public void mergeSort(int[] arr) {
    
}
Copy the code

If the int arr contains no elements or only one element, then there is no sorting at all. I guess 90% of you can write code for the following verification parameters:

public void mergeSort(int[] arr) {
    if (arr.length <= 1)
        return;
}
Copy the code

Tip: Verification parameters are very important, which is the first step in the follow-up process. There are still a large number of students who are anxious about the follow-up implementation and forget the verification parameters.

Now we get down to the really exciting part!

We need to split the array in half and sort it separately. Here’s a twist on merge sort:

  • With some:Where should I store the split subarray?

It’s a tricky point because there are two ways to do it:

  • Idea 1: Create a new storage space for each subarray to store them.

  • Idea 2: Use the original array to hold the subarrays, and use an extra subscript variable to separate them.

Obviously, thought 2 is less storage than thought 1, but thought 1 is probably simpler. Let’s implement ideas 1 and 2, respectively.

Idea 1 how to implement

First we need to cut the original array in half, then create two new arrays, and fill the corresponding elements of the original array into the new array. This code is not difficult to write, as follows:

public void mergeSort(int[] arr) {
    if (arr.length <= 1)
        return;
    int mid = (0 + arr.length-1) /2;

    int[] a1 = new int[mid+1];
    int[] a2 = new int[arr.length-1-mid];

    copyArr(arr, 0, mid, a1);
    copyArr(arr, mid+1, arr.length-1, a2);
}
Copy the code

First we need to calculate the index of the middle element. We can get the index of the middle element by dividing the sum of the initial element index (0 in our example) and the last element index (arr.Length-1 in our example) by 2:

int mid = (0 + arr.length-1)/2;
Copy the code

Then create two arrays A1 and a2:

  • a1To store the subscripts in the original array0tomidOf the elements, totalmid+1An element.
  • a2To store the subscripts in the original arraymid+1toarr.length-1Of the elements, total(arr.length-1) - (mid+1) + 1, that is,arr.length-1-midAn element.

Then copy the elements from the original array with subscripts 0 to mid into the new array A1, and copy the elements from the original array with subscripts mid+1 to arr.Length-1 into the new array A2. CopyArr is a utility method that we created ourselves to copy array elements (the utility method is very simple and won’t talk too much) :

/** * Copy the index element in the source array to the target array * @param source array * @param low source array initial subscript * @param high source array end subscript * @param dest target array */ private void copyArr(int[] source, int low, int high, int[] dest) { for (int i=low; i <= high; i++) { dest[i-low] = source[i]; }}Copy the code

Then we should:

  • Step 1: Sort a subarray;

  • Step 2: Sort another subarray;

  • Step 3: Merge the two ordered subarrays from Step 1 and Step 2 into one ordered array.

Since there are three steps, we need to define three functions, but since steps 1 and 2 are really just sorting an array, we can recursively call the mergeSort function at this point.

For step 3, we can define a new merge method to merge two subarrays into one ordered array, so the mergeSort function now looks like this:

public void mergeSort(int[] arr) {
    if (arr.length <= 1)
        return;
    int mid = (arr.length-1)/2;

    int[] a1 = new int[mid+1];
    int[] a2 = new int[arr.length-1-mid];

    copyArr(arr, 0, mid, a1);
    copyArr(arr, mid+1, arr.length-1, a2);

    mergeSort(a1);
    mergeSort(a2);

    merge(a1, a2, arr);
}
Copy the code

Now that the mergeSort function is complete, all you need to do is implement the Merge method. The merge method is used to merge two ordered arrays into one ordered array, so its prototype should be defined as:

private void merge(int[] s1, int[] s2, int[] dest) {
        
}
Copy the code

Where S1 and S2 are two subarrays, dest is the target array.

The following variables need to be defined:

  • I is the subscript of the first subarray, which initially refers to the beginning element of the first subarray, which is 0.

  • J is the subscript of the second subarray, which initially refers to the beginning element of the second subarray, which is 0.

  • Pos indicates which subscript element of the target array is currently being populated, starting with 0.

We need to fill up the target array, so we introduce a for loop that starts at the beginning of the target array and ends at the end. The code looks like this:

private void merge(int[] s1, int[] s2, int[] dest) { int i = 0; int j = 0; for (int pos = 0; pos < dest.length; Pos++) {// write padding here}}Copy the code

To fill in the contents of the for loop, we need:

  • If s1[I] is smaller than dest[pos], insert s1[I] into dest[pos] and increment I by 1. If s2[j] is small, insert s2[j] into dest[pos] and increment j by 1.

The code could then be written like this:

private void merge(int[] s1, int[] s2, int[] dest) { int i = 0; int j = 0; for (int pos = 0; pos < dest.length; pos++) { if (s1[i] <= s2[j]) { dest[pos] = s1[i++]; } else { dest[pos] = s2[j++]; }}}Copy the code

The code above ignores one of the most important cases: if s1 is traversed first, that is, if I is s1. Length, then s1[I] cannot be accessed. Otherwise, an out-of-bounds exception will be thrown. If s2 is traversed first, that is, if j is s2. Length, then s2[j] cannot be accessed. Otherwise, an out-of-bounds exception will be thrown.

Forgetting boundary conditions is an extremely common and error-prone problem when coding implementation algorithms. For simplicity, we can consider the boundary conditions first and then deal with the general content. In this example, we can first deal with s1 traversal and S2 traversal, and then compare the size of S1 [I] and S2 [j], as shown below:

private void merge(int[] s1, int[] s2, int[] dest) { int i = 0; int j = 0; for (int pos = 0; pos < dest.length; If (I == s1. Length){dest[pos] = s2[j]; if (I == s1. Else if (j == s2.length) {dest[pos] = s1[I ++]; } / / here are normally more else if (s1 [I] < = s2 [j]) {dest (pos) = s1 [i++]; } else { dest[pos] = s2[j++]; }}}Copy the code

Tip: As you can see, the amount of code doubles or more when you add code to determine boundary conditions, but we’ll show you how to use sentinels to significantly reduce the amount of code.

So, we’re done talking about how to do merge sort using idea 1, which is to allocate storage space separately for subarrays, but let’s see how to do merge sort using idea 2.

Idea 2: How to do that

The drawback of idea 1 is that each time mergeSort is called, if the array to be sorted contains more than one element, it needs to be split into two subarrays, and additional storage space needs to be allocated for these two subarrays.

If we don’t want to pay the additional cost, direct use of the original array to store the subarray, then in pairs to sort an array will have to specify the subarray corresponds to what is the start and end the subscript subscript, so we had to define a function for sorting an array, we can call it a mergeSort0, the function prototype is as follows:

private void mergeSort0(int[] arr, int low, int high) {
        
}
Copy the code

Where arr is the original array, low refers to the starting index of the subarray, and high refers to the end index of the subarray.

The merge function, which merges two ordered subarrays into one ordered array, needs to change its parameters as well.

When we split an array into two subarrays, we do the following:

  • The elements from the beginning to the middle belong to a subarray

  • We start with the last element in the middle element, and we end up with the last element in another subarray

We call the index of the beginning element low, the index of the middle element mid, and the index of the end element high. Then the subindex range of the split array is:

  • Low ~ mid belongs to a subarray

  • Mid +1 ~ high belongs to a subarray

When merging subarrays, we only need to know low, mid, and high to know the subarray range, so the prototype of the merge function should look like this:

private void merge(int[] arr, int low, int mid, int high) {

}
Copy the code

With mergeSort0, which sorts subarrays, and merge, which mergeSort0, which merges ordered subarrays, we can rewrite mergeSort as follows:

public void mergeSort(int[] arr) {
    if (arr.length <= 1)
        return;
    int mid = (arr.length-1)/2;
    
    mergeSort0(arr, 0, mid);
    mergeSort0(arr, mid+1, arr.length-1);
    merge(arr, 0, mid, arr.length-1);
}
Copy the code

To implement mergeSort0, the following steps are required:

  • Calibration parameters

  • Split the sorted array into two subarrays

  • So let’s sort 1 subarray

  • Sort another subarray

  • Merges two sorted subarrays into an ordered array

Let’s look at the code below:

Private void mergeSort0(int[] arr, int low, int high) {private void mergeSort0(int[] arr, int low, int high) {return (low >= high); Int mid = (low + high)/2; // Sort a subarray mergeSort0(arr, low, mid); // Sort mergeSort0(arr, mid+1, high); // Merge two sorted subarrays into one ordered array (arr, low, mid, high); }Copy the code

Now that mergeSort0 is done, it’s time to take a look at how the merge function is written, but there is a huge problem: subarrays take up the storage space of the original array!

For example, if an array has four elements [2, 7, 1, 4], its two subarrays are ordered, respectively: [2, 7] and [1, 4], as shown in the following figure:

If we want to merge the two subarrays in the figure above, since the element 1 pointed to by j is smaller than the element 2 pointed to by I, we will place 1 in the first element of the resulting array, which is the original array, and will overwrite the first element 2 of the original array. This is intolerable.

To solve the above problem, we need a temporary storage space to store the ordered subarray contents so that we don’t break the subarray when we write the results back into the original array. This temporary storage space can be created in the merge function, but each time the merge function is called, a temporary storage space is created. It can also be used as a global variable to apply for storage space only once. The latter is obviously more elegant, so we’ll use the latter here.

First we define a member variable named TMP:

private int[] tmp;
Copy the code

Then rewrite the mergeSort function to allocate storage for the TMP array:

Public void mergeSort(int[] arr) {TMP = new int[arr.length]; if (arr.length <= 1) return; int mid = (arr.length-1)/2; mergeSort0(arr, 0, mid); mergeSort0(arr, mid+1, arr.length-1); merge(arr, 0, mid, arr.length-1); }Copy the code

We can then use the TMP array in the merge function (we will not spend a lot of time discussing the merge function in detail since we discussed the implementation of the merge function in detail) :

private void merge(int arr[], int low, int mid, int high) { int i = low; int j = mid+1; For (int pos = low; pos <= high; pos++) { tmp[pos] = arr[pos]; } for (int pos = low; pos <= high; pos++) { if (i == mid+1) { arr[pos] = tmp[j++]; } else if (j == high + 1) { arr[pos] = tmp[i++]; } else if (tmp[i] <= tmp[j]) { arr[pos] = tmp[i++]; } else { arr[pos] = tmp[j++]; }}}Copy the code

Ok, you’re done!

Can we go back and see if there’s anything else we can optimize?

If you take a closer look at the mergeSort and mergeSort0 code, you’ll see that they do very similar things! However, mergeSort specifies a constant 0 for the start element and a constant arr.length-1 for the end element, while mergeSort0 uses the variables low and high instead. When code that does the same thing appears in your program, be sure to see if you can combine the same thing! In this case, the mergeSort code starts with the same call to mergeSort0(arr, 0, arr.Leng-1), so let’s simplify the mergeSort function again:

public void mergeSort(int[] arr) {
    tmp = new int[arr.length];
    mergeSort0(arr, 0, arr.length-1);
}
Copy the code

Okay, this time we’re done!

Summary review

Merge sort algorithm is extremely simple, but the divide-and-conquer idea behind it is so important. Let’s sort out the divide-and-conquer idea again, which is roughly divided into 3 steps:

  1. Divide: To Divide a big problem into smaller problems (inMerge sortIs to split the sorted array into 2 subarrays.
  2. Conquer: Continue to Conquer small problems using recursion until they are small enough to be easily solved (inMerge sortIf the subarray is broken down to one element, then that element must be ordered.
  3. Combine: The combination of solved sub-problems to solve larger problems (inMerge sortTo merge sorted subarrays into an ordered array.

In addition, in the specific merge sort, you need to pay attention to the following problems:

  • It is necessary to verify the parameters

  • In the loop, pay attention to the judgment of boundary conditions. You can write the special case clearly before writing the general case

  • How do I compute the middle element of an array and how do I partition an array? What’s the difference between taking (start subscript + end subscript)/2 and just using the array length /2?

  • How do I store subarrays? Do YOU want to use extra storage, or do you want to store it in the original array with the start and end indices?

  • Combine code when you encounter code that has the same function

Ok, so that’s a little bit of thinking about implementing merge functions, and HOPEFULLY it’ll be helpful.

We are all little frogs, ribbit ribbit ribbit

Make an advertisement for a children’s book

  • How MySQL works: Understanding MySQL from the root: juejin.cn/book/684473…

  • How to use MySQL: learning MySQL from scratch: juejin.cn/book/684473…

  • How Computers Work: Understanding Computers from the Root: juejin.cn/book/684473…

  • How MySQL Works: Finding Ways to Understand MySQL

    Jingdong link: u.jd.com/1Mldwv9

    Dangdang link: u.dangdang.com/qRPRW