对于一个int数组，请编写一个归并排序算法，对数组元素排序。
给定一个int数组A及数组的大小n，请返回排序后的数组。
测试样例：
[1,2,3,5,3],6
[1,5]

思路：合并两个有序数组即可。
1， 接口为mergeSort(int * A,int n)，要将其转化为递归问题来做
2， 在merge的时候，需要申请零时空间int * pA；记得要delete掉。

#include<iostream>
#include<string>
using namespace std;


class MergeSort {
public:
    void print(int * A,int n){
        for (int i = 0; i < n; i++)
            printf("%d ",A[i]);
        printf("\n");
    }

    //[start,mid]有序,(mid,end]有序，将两个有序数组合并即可
    void merge(int * A,int start,int mid,int end){
        //需要搞一个零时变量
        int n = end - start + 1;
        int * pA = new int[n];

        int s_index = start;
        int end_index = mid + 1;
        int index = 0;
        while (s_index <= mid && end_index <= end){
            if (A[s_index] < A[end_index]){
                pA[index++] = A[s_index++];
            }
            else{
                pA[index++] = A[end_index++];
            }
        }

        while (s_index <= mid){
            pA[index++] = A[s_index++];
        }

        while (end_index <= end){
            pA[index++] = A[end_index++];
        }

        index = 0;
        for (int i = start; i <= end; i++){
            A[i] = pA[index++];
        }
        delete[] pA;
    }

    //对应的是index
    int * mergeSort1(int * A,int end){
        if (start >= end){
            return A;
        }

        int mid = (start + end) / 2;
        mergeSort1(A,start,mid);
        mergeSort1(A,mid + 1,end);
        merge(A,mid,end);
        return A;

    }

    //应该在原位置做排序
    int* mergeSort(int* A,int n) {
        // write code here
        mergeSort1(A,0,n - 1);
        return A;
    }
};


int main()
{
    MergeSort s;

    int A[] = { 1,2,3,5,3 };
    int n = 6;
    s.mergeSort(A,n);
    s.print(A,n);

}