Thoughts:

The sequence to be sorted is divided into two subsequences, and then the two subsequences are recursively continued until the sequence is ordered, that is, there is only one element in the sequence, and then all the ordered subsequences are merged into a whole ordered sequence layer by layer. Each merge is to merge two ordered tables into one ordered table.
The picture shows:

Specific realization:

1. The sequence to be sorted is divided into two sub-sequences, and then the sub-sequences are allowed to continue the molecular sequence.
2. Merge two subsequences separated from the same sequence.

• To apply for memory space, the space size is the sum of two sorted sequences, which is used to temporarily store the merged sequences.
• Set two pointer variables to the starting position of two sorted column arrays.
• Repeat the previous step until a pointer reaches the end of the sequence.
• When one pointer reaches the end of the sequence, the elements in another sequence are copied directly to the end of the merged sequence.
• Copy the elements in the merged sequence to the proper position of the original combination.
  Code implementation:
  

package www.sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {9,2,5,7,3,8,3,6,1};
        mergeSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
    public static void mergeSort(int[] array,int left,int right){
        if (left >= right){
            return;
        }
        int mid = left+(right-left)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,right,mid);
    }
    public static void merge(int[] array,int left,int right,int mid){
        int[] extra = new int[array.length];
        int m = mid+1;
        int l = left;
        int x = left;
        while (left <= mid && m <= right){
            if (array[left] <= array[m]){
                extra[x++] = array[left++];
            }else {
                extra[x++] = array[m++];
            }
        }
        while (left <= mid){
            extra[x++] = array[left++];
        }
        while (m <= right){
            extra[x++] = array[m++];
        }
        while (l <= right){
            array[l] = extra[l++];
        }
    }
}