可能简单的归并排序

//归并排序

将原始数组A[0:n-1]中的元素分成两个大小大致相同的子数组：A[0:n/2]和A[n/2+1:n-1]，分别对这两个子数组单独排序，然后将已排序的两个数组归并成一个含有n个元素的有序数组。（不断地进行二分，直至待排序数组中只剩下一个元素为止，然后不断合并两个排好序的数组段）

void MergeArr(int* a, int begin1, int end1, int begin2, int end2, int* tmp)//归并
{
    int left=begin1, right=end2;
    int index = begin1;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[index++] = a[begin1++];
        }
        else
        {
            tmp[index++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = a[begin2++];
    }
    for (int i = left; i <= right; ++i)
    {
        a[i] = tmp[i];
    }
}
void _MergeSort(int* a, int left,int right,int*tmp)
{
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) / 2;

    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid+1,right, tmp);

    MergeArr(a, left, mid, mid + 1, right, tmp);
}

void MergeSort(int* a, int n)
{
    assert(a);

    int* tmp = (int*)malloc(sizeof(int) * n);

    _MergeSort(a, 0, n - 1, tmp);

    free(tmp);
}