一、归并排序

归并排序的思想是：依次把数组分成若干个小组进行排序，然后逐步把每个小组进行排序合并。

最经典的介绍归并排序的示例图为：

第一步：把8个元素分别分成4个小组排序，得到1, 2/3, 4/5, 6/7, 8四组。

第二步：把1, 2和3, 4合并，5, 6和7, 8合并，得到1, 2, 3, 4和5, 6, 7, 8两组。

第三部：把剩下的两组合并，得到有序的数组1 2 3 4 5 6 7 8，排序完成

归并排序的时间复杂度为O(lgn)

二、合并两个有序数组

合并两个有序数组需要用到一个辅助数组，保存排序后的元素。具体的逻辑是：分别使用两个指针，指向两个数组的首端，比较两个指针指向的元素，把小的放到辅助数组里面，指针后移，重复上面的操作。

例如上面合并1, 2, 3, 4和5, 6, 7, 8两组元素，设置指针i和j分别指向两个数组，此时a[i] > b[j]，把b[j]放到数组里面去：

然后依次执行，直到b数组中的元素放完：

再把a中所有的元素放到有序数组中去，排序就完成了：

合并部分的代码：

// mid是i的结束位置，right是j的结束位置，tmp是临时数组
while (i <= mid && j <= right) {
    if (data[i] <= data[j])
        tmp[k++] = data[i++];
    else
        tmp[k++] = data[j++];
}

三、归并排序实现

/*
 * @data 待排序数组
 * @tmp 临时数组
 * @left 当前需要排序的区间开始
 * @right 当前需要排序的区间结束
 */
static void _merge_sort(int *data, int *tmp, uint left, uint right) {
    uint mid, i, j, k, cur;
    if (left == right)
        return;

    mid = (left + right) / 2;
    i = left;
    j = mid + 1;
    k = left;
    
    // 分组排序
    _merge_sort(data, tmp, left, mid);
    _merge_sort(data, tmp, mid + 1, right);

    // 合并有序分组
    while (i <= mid && j <= right) {
        if (data[i] <= data[j])
            tmp[k++] = data[i++];
        else
            tmp[k++] = data[j++];
    }

    // 处理两个数组多余的元素
    while (i <= mid)
        tmp[k++] = data[i++];
    while (j <= right)
        tmp[k++] = data[j++];

    // 拷贝已经排好序的到正式需要排序的数组
    for (i = left; i <= right; i++)
        data[i] = tmp[i];
}

/*
 * @data 待排序数组
 * @len 数组长度
 */
void merge_sort(int *data, const uint len) {
    // 为临时数组分配空间
    int *tmp = malloc(sizeof(int) * len);
    if (tmp == NULL)
        return;

    _merge_sort(data, tmp, 0, len - 1);

    // 删除临时数组的空间
    free(tmp);
    tmp = NULL;
}