Merge Sort

归并排序，将两个或两个以上的有序序列组合成一个新的有序序列。

下边这种将被排序表分成$ \lceil n/2 \rceil$个长度为2或1的有序表，然后再两两归并。被称作二路归并排序。

下边是二路归并排序代码:

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;

// 将[low, mid] 和 [mid+1, high]合成一个有序表
void merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    int B[high] = {0}; // 定义辅助数组
    for (k = low; k <= high; k++)
        B[k] = A[k]; // 将A中元素复制到辅助数组B中
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
    {
        if (B[i] <= B[j]) // 将较小值复制到A中
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }

    // 对剩余的元素进行复制
    while (i <= mid) A[k++] = B[i++];
    while (j <= high) A[k++] = B[j++];
}

void mergeSort(int A[], int low, int high)
{
    if (low < high)
    {
        int mid = low + (high - low) / 2; // 划分序列
        mergeSort(A, low, mid);           // 对左子序列进行递归排序得到一个有序序列
        mergeSort(A, mid + 1, high);      // 对右子序列进行递归排序得到一个有序序列
        merge(A, low, mid, high);         // 对最终的两个有序序列进行归并
    }
}

int main(int argc, char *argv[])
{
    int R[] = {1, 3, 2, 3, 53, 532, 52, 5, 67, 68};
    dbg(R);
    int len = sizeof(R) / sizeof(R[0]);
    mergeSort(R, 0, len - 1);
    dbg(R);
    return 0;
}

运行结果:

时间复杂度 $\color{blue}{O(nlog_2n)}$

1. (函数mergeSort)一共要执行$O(log_2n)$次排序，类似二分查找
2. (函数merge)每趟归并排序时间复杂度为$O(n)$

空间复杂度$\color{blue}{O(n)}$: merge()中辅助数组B占用n个单元，故为$O(n)$.