排序算法（归并排序）

归并排序是一种基于递归进行的一种排序算法
其：

空间复杂度为 O(n)，时间复杂度为 O(nlogn)

归并排序是分治法思想运用的一个典范

如下图可以先将待排序数组分为两部分，之后在分别对这两部分进行排序。简单来说就是大事化小。

图解

所谓递归其实就和它的名字一样先递推出去再回归回来。
归并排序就恰好和递归思想一致，先是将待排序数组进行拆分直到拆成一个个独立的数，也就可以联想到递归的“递”：

接下来继续上面的操作直到不可再分

将其拆分完成后只需要加一个排序函数就可以利用递归的“归”将其改为你想要的顺序：

递归排序C代码：

void Sort(int *arr, int left, int mid, int right)//排序函数
{
   
   
    int tmp[right-left+1];
    int l = left;
    int m = mid + 1;
    int i = 0;
    int j = 0;

    while(l <= mid && m <= right)
    {
   
   
        if (arr[l] > arr[m])
        {
   
   
            tmp[i++] = arr[m++];
        }
        else 
        {
   
   
            tmp[i++] = arr[l++];
        }        
    }
    while(l <= mid)
    {
   
   
        tmp[i++] = arr[l++];
    }
    while(m <= right)
    {
   
   
        tmp[i++] = arr[m++];
    }
    for (i = 0, j = left; j <=right; i++, j++)
    {
   
   
        arr[j] = tmp[i];
    }
}

void MergeSort(int *arr, int left, int right)//递归主体
{
   
   

    if (left >= right)
    {
   
   
        return;
    }
    int mid = (left + right) / 2; 
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Sort(arr, left, mid, right);
}

int main()        //主函数
{
   
   
    int arr[10] = {
   
   3,4,7,5,2,6,9,8,0,13};
    MergeSort(arr, 0, 9);
    return 0;
}