代码

要求：

对于一个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) {
        // write code here
        if(n<2){
            return A;
        }
        int* temp = new int[n];  //这里是重点，一个协助数组
        mergeSortRec(A,0,n-1,temp);
        return A;
    }
    
private:
    void mergeSortRec(int* A, int first, int last, int* temp){
        if(first<last){
            int mid = (first+last)/2;
            mergeSortRec(A, first, mid, temp);
            mergeSortRec(A, mid+1, last, temp);
            mergeArray(A, first, mid, last, temp);
        }
    }
    
    void mergeArray(int* A, int first, int mid, int last, int* temp){
      int i = first, j= mid+1,k=first;
      while((i<=mid)&&(j<=last)){
          if(A[i]<A[j]){
              temp[k++]=A[i++];
          }else{
              temp[k++]=A[j++];
          }
      }
      while(i<=mid){
          temp[k++]=A[i++];
      }
      while(j<=last){
          temp[k++]=A[j++];
      }
      for(i=first;i<=last;i++){ //第一次没有没有通过测试，是因为这里简单的把temp付给了A,即：A=temp
          A[i]=temp[i];
      }
    }
};

要点：

• 最重要的还是递归思想，并且要能设计合理的递归函数

• 非递归的方法也可是实现，回头我给补上。