归并排序

算法

1. 对输入的序列，按数组的中间点进行划分，分为左、右两个子序列
2. 递归的划分直至每个子序列都只有一个元素
3. 把划分的左、右子序列合并、排序，返回归并后的子序列（作为上一层的左右子序列）

递归划分过程：

归并过程：

C++实现

// p为输入的数组，l为数组左端点，r为右端点

void merge_sort(int p[], int l, int r) {
    if (l >= r) return; // 递归到只有merge_sort(p,x,x)的时候，直接返回该子序列
                        // 单个元素不用排序，然后交给后面排序这2个子序列

    int mid = (l + r) >> 1; // 取序列下标中点

    merge_sort(p, l, mid); // 递归的归并排序左边子序列
    merge_sort(p, mid + 1, r); // 递归的归并排序右边子序列

    // 此时返回回来的左、右序列都是已经排序好了，我们要在开辟的一个临时的数组空间中，将其归并、按顺序合二为一
    // 这里利用双头双指针（区别于头尾双指针，在原数组上操作）
    int k = 0, i = l, j = mid + 1;  // k为在临时数组空间的下标（元素个数），l初始化指向左子序列的头，j初始化指向右子序列的头

    // 将左、右子序列中从左到右较小的元素存入临时数组空间，直至其中一个序列到达边界
    while (i <= mid && j <= r)
        if (p[i] <= p[j]) tmp[k++] = p[i++];
        else tmp[k++] = p[j++];
    // 将另一个未到达边界的序列剩余的元素存入临时数组空间末尾
    while (i <= mid) tmp[k++] = p[i++];
    while (j <= r) tmp[k++] = p[j++];
    // 将临时数组空间排好序的序列覆盖到原数组
    for (i = l, j = 0; i <= r; i++, j++) p[i] = tmp[j];
}

复杂度

• 时间复杂度为nlog(n)
• 空间复杂度为2n