归并排序

1. 主要思想

归并排序算法的主要思想：分治

2. 归并排序的步骤

1. 确定分界点

   • 以数组的中间位置为分界点，分为左右两部分。

   • mid = (l + r) / 2

2. 递归排序左右两部分

   • 递归左右两部分，对最小的单位进行排序

3. 归并——合二为一（重难点）

   • 把两个有序的数组合并为一个有序的数组

• 时空复杂度：
  • 时间复杂度：\(O(nlog_2n)\)
  • 空间复杂度：\(O(n)\)

3. 实现过程（双指针算法）

图片摘自：http://t.csdn.cn/RNb0o

4. 模板

void merge_sort(int q[], int l, int r) {
    // 判断当前区间是否只有一个数或者没有数
    if (l >= r) return;
    int mid = l + r >> 1;
    // 递归排序子数组
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    // 排序当前数组
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    // 处理某数组的元素全部排序完成，另一个数组中包含元素的情况
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    // 把临时数组中排好序的内容转移到要排序的数组
    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}