经典排序算法——归并排序

对于一个int数组，请编写一个归并排序算法，对数组元素排序。

给定一个int数组A及数组的大小n，请返回排序后的数组。

[1,2,3,5,2,3],6

[1,2,2,3,3,5]

class MergeSort {
public:
    int* mergeSort(int* A, int n) {
        if(A==NULL||n<2)
            return A;
        process(A,0,n-1);
        return A;
    }
    
    void process(int* A,int left,int right)
    {
        if(left>=right)
            return;
        int mid=left+(right-left)/2;
        //划分左右
        process(A,left,mid);
        process(A,mid+1,right);
        //合并左右
        merge(A,left,mid,right);
    }
    
    void merge(int* A,int left,int mid,int right)
    {
        int* temp=new int[right-left+1];//临时数组
        int l=left,r=mid+1;
        int k=0;
        while(l<=mid && r<=right) //临时数组选取左、右子数组中较小的
        {
            if(A[l]<A[r])
                temp[k++]=A[l++];
            else
                temp[k++]=A[r++];
        }
        while(l<=mid)   temp[k++]=A[l++];//将剩余的数直接复制到临时数组中
        while(r<=right) temp[k++]=A[r++];
        
        //将临时数组放回原数组相应位置
	    for (int i = 0; i <right-left+1; i++) 
        {
			A[left + i] = temp[i];
		}
        delete[] temp;
    } 
};