This is the 18th day of my participation in Gwen Challenge

Sorting in engineering applications has a very important role, for example, you randomly click open a search engine, through the search results are sorted processing; You participate in the Internet e-commerce seconds kill activity, after the user request arrives at the server, the server program will sort according to the request arrival time processing. In database design, the order of fields also affects our query performance.

So, it’s no surprise that interview questions about sorting algorithms come up, and I’m going to look at one of the most common sorting algorithms that comes up in interviews: merge sort

Merge sort

Merge sort is an effective way to sort the elements in an array. It’s a pretty classic sorting algorithm that you learned in school. But instead of using the textbook approach, we’re going to use a combination of binary trees. Merge sort is very similar in nature to the back-order traversal of a binary tree.

Post-order traversal has an important feature: get the information of the subtree, use the information of the subtree, and integrate the information of the whole tree.

If we think of order as information, merge sort is essentially a back-order traversal.

This can be expressed in pseudocode as follows:

Sub_info = substructure (subtree/subarray) full_info = integration (sub_info)Copy the code

So merge sort/post order traversal test points can be summarized as the following 3 points:

  • How do you divide substructures
  • Get information about substructures
  • Using the information of substructure, integrate the information of whole tree

So let’s start with these three things. And look at it in contrast to the code for the postorder traversal of the binary tree.

Before we start talking about the topic, let’s look at the open close principle. In fact, most languages are designed according to this principle. For example, if the first element of an array is subscript 0, then an array of length N needs to be represented by an open and closed interval [0, n].

And just to make it easier to handle, the length of the interval is just the right boundary minus the left boundary. For example, the interval length of [0, 10) is 10, but if the double-closed interval is used, such as [0, 9], then the running formula for the interval length is: 9-0 + 1, and 1 needs to be added on the basis of the subtraction.

1. The division

So first let’s see how we do an array of numerators. For binary trees, subtree partitioning is natural and has been specified in data structures, such as treenode. left and treenode. right.

However, for an array, the efficiency of cutting the array into an average half should be the highest if the optimal efficiency is to be achieved during the partitioning (which can be associated with the efficiency of a binary balanced tree).

Binary trees are written as follows:

Root. left, root.right; This can be obtained directly from the root structure information.Copy the code

Merge sort is written as follows:

Final int m = b + ((e-b)>>1); final int m = b + (e-b)>>1); Array A, [m, e) => indicates the left subarray.Copy the code

2. Information about subarrays

Since we’re sorting, we need to sort the left subarray and the right subarray respectively. If you remember from lecture 06 that we talked about “backward traversal of binary trees,” sorting subarrays is just recursive.

// postOrder(root.left); // postOrder(root.left); postOrder(root.right);Copy the code

Merge sort is written like this:

Merge_sort (a, b, m); merge_sort(a, m, e);Copy the code

3. Integration of information

Next, we need to process the information from the subtree/subarray. Different needs will lead to different processing methods. For merge sort, we need to merge two ordered subarrays into one large ordered array.

Finally, there are boundaries to consider:

  • When b >= e, it indicates that this interval is an empty interval and there is no need to sort again.
  • When b plus 1 is equal to e, there’s only one element, and there’s no need to sort.

The above two boundary cases can be respectively corresponding to the case when the binary tree is empty and the binary tree has only one node.

The complete code

At this point, we can write the code for merge sort (explained in the comment) :

class Solution {
  private void msort(int[] a, int b, int e, int t[]) {
    // Empty interval or only one element
    // Use b >= e to prevent overflow of b + 1
    if (b >= e || b + 1 >= e) {
      return;
    }
    // Binary tree can automatically obtain root. Left, root. Right
    // Here we need to compute the left and right subarrays.
    final int m = b + ((e - b) >> 1);

    // Parallel binary tree traverses the left and right subtrees respectively.
    msort(a, b, m, t);
    msort(a, m, e, t);
    // I refers to the beginning of the left subarray and j refers to the beginning of the right subarray
    // to points to the position where t corresponds to the interval [b, e]
    int i = b;
    int j = m;
    int to = b;

    // Merge the two subarrays. Note that the following is an important template
    // The judgment bar here is as long as there are elements in both subarrays
    while (i < m || j < e) {
      // If the right subarray has no elements or the left subarray begins with an element smaller than the right subarray begins with an element
      // Remove the element at the beginning of the left subarray
      <= a[j] = a[j] = a[j] = a[j] = a[j] = a[j] = a[j] = a[j] = a[j] = a[j]
      if (j >= e || i < m && a[i] <= a[j]) {
        t[to++] = a[i++];
      } else {
        // Take the element at the beginning of the right subarrayt[to++] = a[j++]; }}// Copy the result of the merge to the original array a[]
    for(i = b; i < e; i++) { a[i] = t[i]; }}public void mergeSort(int[] nums) {
    // If the array passed in is empty
    if (nums == null || nums.length == 0) {
      return;
    }
    // t is a transient array
    int[] t = new int[nums.length];
    msort(nums, 0, nums.length, t); }}Copy the code

Complexity analysis: time complexity O(NlgN), space complexity O(N).

summary

Merge sort:

  • How to split left and right subarrays;
  • How to merge, pay attention to the conditions of the loop when merging, and the writing method of stable sorting;
  • Open and close principle.