Introduction to the

Merge Sort is an efficient and stable sorting algorithm based on Merge operations. It is a typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called binary merge.

Time complexity

O(nlogn)

Thought analysis

Order: From smallest to largest

Divide an array into elements, and finally combine each element into two groups and two groups in order, and the final array is an ordered array.

Merge sort is actually not that hard, but when it comes to recursive splitting, it’s hard for people who don’t have a lot of recursion to understand how it works, and once you understand how it works recursively, so does the merge algorithm. Merge algorithm uses the idea of divide and conquer, divide first and conquer later. The following figure shows the divide-and-conquer process and the recursive execution order:

The last merge in the figure above is to merge the ordered subsequences [4,5,7,8] and [1,2,3,6] into the final sequence [1,2,3,4,5,6,7,8]. The following is the merge process (the last merge process is the same as the previous n merge process).

It is recommended to simply look at the diagram, read the code again, and then combine the diagram and code to understand, it will be easier to understand.

Code implementation

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8.4.5.7.1.3.6.2};
        mergeSort(arr, 0, arr.length - 1.new int[arr.length]);
        System.out.println(Arrays.toString(arr));
    }

    /** * split **@paramArr Array to split *@paramLeft Start index * of the array to be split@paramRight End index of the array to be split *@paramTemp merges the temporary array */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            / / mid analysis
            // left + right >> 1 = mid left partial index right partial index
            // 0 + 8 >> 1 = 4
            // 0 + 7 >> 1 = 3
            int mid = (left + right) >> 1;
            // Split the left part
            mergeSort(arr, left, mid, temp);
            // Split the right part
            mergeSort(arr, mid + 1, right, temp);
            / / mergemerge(arr, left, mid, right, temp); }}/** * merge **@paramArr Array to merge *@paramLeft The array to be merged starts the index *@paramMid Specifies the middle index of the array to be merged@paramRight End index * of the array to be merged@paramTemp merges the temporary array */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // The current index of left-mid
        int lIndex = left;
        // the current index of mid+1-right
        int rIndex = mid + 1;
        // Compare the current index of temp during the process
        int tIndex = 0;
        // 1. The left-mid and mid+1-right elements are added to temp
        while (lIndex <= mid && rIndex <= right) {
            if (arr[lIndex] < arr[rIndex]) {
                temp[tIndex] = arr[lIndex++];
            } else {
                temp[tIndex] = arr[rIndex++];
            }
            tIndex++;
            // The above statement can be shortened to the following statement
            // temp[tIndex++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++] : arr[right++];
        }

        // 2. The elements in left-mid and mid+1-right May be uneven. The elements in left-mid or mid+1-right May be left
        // Since the elements in left-mid and mid+1-right are ordered, they can be filled directly into temp
        // if the left-mid is left, the loop will enter
        while (lIndex <= mid) {
            temp[tIndex++] = arr[lIndex++];
        }
        // if (mid+1-right) is left in the loop
        while (rIndex <= right) {
            temp[tIndex++] = arr[rIndex++];
        }

        // 3. Copy temp to arR after temp is merged into temp
        while (tIndex > 0) { arr[right--] = temp[--tIndex]; }}}Copy the code

conclusion

Merge algorithm is a stable algorithm, its merge times is N-1 times, that is to say, when there are 1000 elements, only 999 times need to merge, sorting speed is very fast.

Merge sort is all about understanding the recursive process, and if you understand the recursive process, you understand merge sort. Merge sort, because of the recursion, takes up space, which is space for time.