Sort merge sort

1. The basic idea

Merge sorting is an effective sorting algorithm based on merge operation . The algorithm is a divide-and-conquer method （Divide and Conquer） A very typical application . Merges ordered subsequences , You get a perfectly ordered sequence ; So let's make each subsequence in order , Then make the subsequence segments in order . If two ordered tables are merged into one ordered table , be called 2- Road merging .

2. Add : Divide and conquer method :

​ When solving an input scale of n, and n When there is a big problem in the value of , Direct solution is often very difficult . At this time , You can first analyze some characteristics of the problem itself , Then start from these characteristics , Choose some appropriate design strategies to solve . for example , If you put n Input is divided into k A subset of , Solve these subsets respectively , Then combine the obtained solutions , So we can get the solution of the whole problem , such , Sometimes you can get good results . This method , It's the so-called divide and conquer .
​ Generally speaking , Divide and conquer is to divide the problem into several sub problems to deal with . These sub questions , The structure is the same as the original problem , But it is smaller in scale than the original . If the obtained sub problem is relatively large , Divide and conquer strategies can be used repeatedly , Divide these sub problems into smaller ones 、 Subproblems with the same structure . such , You can use recursive methods to solve these sub problems respectively , And combine the solutions of these subproblems , So as to obtain the solution of the original problem .

3. Dynamic diagram demonstration

4. Algorithm description

• Put the length to n The input sequence of is divided into two lengths n/2 The subsequence ;

• Merge and sort these two subsequences respectively ;

• Merge two sorted subsequences into a final sorted sequence .

• Pictured :

​
You can see that this structure is very similar to a complete two pronged tree , In this paper, we use recursion to implement merging and sorting （ It can also be implemented in an iterative way ）. branch The stage can be understood as the process of recursively splitting the molecular sequence , The recursion depth is log2n.

Look again. cure Stage , We need to combine two ordered subsequences into an ordered sequence , For example, the last merge in the figure above , To put [4,5,7,8] and [1,2,3,6] Two ordered subsequences , Merge into final sequence [1,2,3,4,5,6,7,8], Let's take a look at the implementation steps .

package com.igeek.sort;
import java.util.Arrays;
public class MergeSort {
    
    public static void main(String []args){
    
        int []arr = {
    9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int []arr){
    
        int []temp = new int[arr.length];// Before sorting , First, create a temporary array whose length is equal to the length of the original array , Avoid frequent space creation in recursion 
        sort(arr,0,arr.length-1,temp);
    }
    
    private static void sort(int[] arr,int left,int right,int []temp){
    
        if(left<right){
    
            int mid = (left+right)/2;//
            sort(arr,left,mid,temp);// Left merge sort , Make left subsequence ordered 
            sort(arr,mid+1,right,temp);// Merge and sort on the right , Make the right subsequence ordered 
            merge(arr,left,mid,right,temp);// Merge two ordered subarrays 
        }
    }
    private static void merge(int[] arr,int left,int mid,int right,int[] temp){
    
        int i = left;// Left sequence pointer ( A pointer is a variable that holds the storage address of an object )->index;
        int j = mid+1;// Right sequence pointer 
        int t = 0;// Temporary array pointer 
        while (i<=mid && j<=right){
    
            if(arr[i]<=arr[j]){
    
                temp[t++] = arr[i++];
            }else {
    
                temp[t++] = arr[j++];
            }
        }
        while(i<=mid){
    // Fill the remaining elements on the left with temp in 
            temp[t++] = arr[i++];
        }
        while(j<=right){
    // Fill the remaining elements of the right sequence into temp in 
            temp[t++] = arr[j++];
        }
        t = 0;
        // take temp Copy all the elements in to the original array 
        while(left <= right){
    
            arr[left++] = temp[t++];
        }
    }
}

summary

Merge sort is stable sort , It's also a very efficient sort , Sorting that can take advantage of the full binary tree feature is generally not too bad .java in Arrays.sort() We have adopted a method called TimSort Sort algorithm , It's an optimized version of merge sort . As can be seen from the figure above , The average time complexity of each merge operation is O(n), The depth of a complete binary tree is 0 |log2n|. The total average time complexity is O(nlogn). and , The merge order is the best , The worst , The average time complexity is O(nlogn).