递归的思维和归并排序

第一、思维图如下：

image.png

第二、 代码区块如下：

class MergeSort {
public:
    int* mergeSort(int* A, int n) {
        // write code here
        _mergeSort(A,0,n-1);
        return A;
        
    }
    
    static void _mergeSort(int* _A,int _left,int _right){
        
        if(_left <_right)
            {
            int _middle=(_left + _right)/2;
            _mergeSort(_A,_left,_middle);
            _mergeSort(_A,_middle+1,_right);
            
            _merge(_A,_left,_middle,_right);
        }

    }
    
    static void _merge(int* _A,int _left,int _middle,int _right){
        
        int *L=new int[_middle - _left + 2];
        int *R=new int[_right - _middle + 1];
        
        
        for(int i=_left,x=0;i<=_middle;i++,x++){
            L[x]=_A[i];
        }
        
        for(int i=_middle+1,y=0;i<=_right;i++,y++)
            {
            R[y]=_A[i];
        }
        
        L[_middle - _left + 1]=INT_MAX;
        R[_right - _middle]=INT_MAX;
        
        int x=0,y=0;
        for(int i=_left;i<=_right;i++){
            if(L[x]<R[y]){
                _A[i]=L[x++];
            }
            else{
                _A[i]=R[y++];
            }
            
        }
        
        ////end of _merge.
    }

};