Merge sort is a divide and conquer algorithm. Using recursion, a large data set is decomposed into small subsets. The subsets are ordered and then merged. Merge sort is not an in-situ sort algorithm because it uses temporary space, which is also the main reason why merge sort is not widely used in quick sort. Although the time complexity of merge sort is O (log n) at best and worst. However, this also depends on the use scenario. If the space is exchanged for time, I think this algorithm also has some use. Let's take a look at the code implementation of java

public static void main(String[] args) {
        int[] arr = new int[]{10, 7, 8, 9, 1, 5};
        mergeSort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int n) {
        mergeSortInternally(arr, 0, n - 1);
    }

    private static void mergeSortInternally(int[] arr, int p, int r) {
        if (p >= r) {
            return;
        }
        //find middle point
        int q = p + (r - p) / 2;
        //Recursively decompose the index of array elements and process the first half
        mergeSortInternally(arr, p, q);
        //Processing the second half
        mergeSortInternally(arr, q + 1, r);

        mergeBySentry(arr, p, q, r);
    }
    /**
    * Common merge algorithm
    */
    private static void merge(int[] arr, int p, int q, int r) {
        //Start subscript of the left half array
        int i = p;
        //Starting subscript of the right half array
        int j = q + 1;
        //Starting subscript of temporary array
        int k = 0;
        //Initialize a temporary array with the same size as the current one
        int[] temp = new int[r - p + 1];
        while (i <= q && j <= r) {
            //Compare the starting values of the left and right arrays, and put the smaller element in the first position of the temporary array
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        //The two split arrays are probably not evenly distributed, so one array may be traversed first,
        //Another array has data that has not been compared. At this time, you can directly add the data of the array that has not been compared to the temporary array
        //To initialize the subscript, first initialize the subscript to the array of the left half
        int start = i;
        int end = q;
        //It indicates that the right half is not completely compared. At this time, the subscript is reset to the array of the right half
        if (j <= r) {
            start = j;
            end = r;
        }
        //Add the uncompleted ordered array directly to the temporary array
        while (start <= end) {
            temp[k++] = arr[start++];
        }
        //Copy the data of the temporary array to the original array
        for (i = 0; i <= r - p; i++) {
            arr[p + i] = temp[i];
        }
    }

    /**
     * The merging algorithm of sentinel nodes is added
     *
     * @param arr
     * @param p
     * @param q
     * @param r
     */
    private static void mergeBySentry(int[] arr, int p, int q, int r) {
        //Initialize the temporary space corresponding to the left array and add the position of a sentinel node
        int[] leftArr = new int[q - p + 2];
        //Initialize the temporary space corresponding to the array on the right and add the position of a sentinel node
        int[] rightArr = new int[r - q + 1];

        //Copy the data on the left of the original array to the temporary array
        for (int i = 0; i <= q - p; i++) {
            leftArr[i] = arr[p + i];
        }
        //Add sentinel node to the left array
        leftArr[q - p + 1] = Integer.MAX_VALUE;
        //Copy the data on the right of the original array to the temporary array
        for (int i = 0; i < r - q; i++) {
            rightArr[i] = arr[q + 1 + i];
        }
        //Add sentinel node to the right array
        rightArr[r - q] = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        int k = p;
        while (k <= r) {
            //When the left node is smaller than the right node, the ordered temporary spatial data is added to the original array. When i reaches the sentinel node, i will not increase, but only j
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
    }

The key point here is the implementation logic of merge function. I have posted two implementations of merge function.
One is the original merge implementation. The method name is merge
The other is an improved version, which adds a sentinel node. The method name is mergeBySentry.
The improved version is obviously easier to understand. In the case of critical value, please pay attention to the use of sentinel node, which can make the code logic clearer.

Last java implementation of quick sorting , we talked about the real logic of quick sort. These two sorts are often compared together. Do you think there is any difference between these two kinds of implementation logic? The main differences are:
Merging and sorting is to disassemble big problems into small problems, then deal with small problems, and finally merge small problems.
Quick sorting is to deal with small sorting intervals first, and then deal with big problems slowly.
The two sorting principles are quite different

(the code for merging and sorting mainly comes from the column of geek time < the beauty of data structure and algorithm ". If you are interested in algorithms, you can subscribe to this column. The column is of high quality)