經典排序算法——歸並排序

經典排序算法——歸並排序

對於一個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]) else="" for="" int="" i="0;" left="" pre=""><p>
</p>
   
</a[r])>