对于一个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>@H_502_13@
#include<string>@H_502_13@
using namespace std;


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

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

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

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

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

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

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

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

    }

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


int@H_502_13@ main()
{
    MergeSort s;

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

}