归并排序

把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。经常被使用的是二路归并算法，即将两个已经排序的序列合并成一个序列的操作
时间复杂度：O(n * log n) 数据不敏感
空间复杂度：O(n)
稳定性：稳定
时间复杂度计算过程：
$T[n]=2T[n/2]+n=2^2T[n/2^2]+2n=2^3T[n/2^3]+3n=...=2^mT[1]+mn$
此时$n=2^m \qquad m=log\,n$
得$T[n]=nT[1]+n\;log\,n$
所以归并排序时间复杂度为O(n * log n)

void Merge(int array[], int low, int mid, int high, int extra[]) {
    // [low, high)

    int i = low; // [low, mid)
    int j = mid; // [mid, high)
    int k = low; // extra[low, high)

    while (i < mid && j < high) {
        if (array[i] <= array[j]) {	// =保证了稳定性
            extra[k++] = array[i++];
        } else {
            extra[k++] = array[j++];
        }
    }

    while (i < mid) {
        extra[k++] = array[i++];
    }

    while (j < high) {
        extra[k++] = array[j++];
    }

    for (int x = low; x < high; x++) {
        array[x] = extra[x];
    }
}

void MergeSortInner(int array[], int low, int high, int extra[]) {
    if (high - low <= 1) {
        // size <= 1
        return;
    }

    // 1. 平均切割
    int mid = low + (high - low) / 2;
    // 2. 分治处理左右两个小区间
    MergeSortInner(array, low, mid, extra);  // [low, mid)
    MergeSortInner(array, mid, high, extra); // [mid, high)
    // 3. 合并两个有序数组
    Merge(array, low, mid, high, extra);
}

// 递归实现
void MergeSort(int array[], int size) {
    int* extra = (int*)malloc(sizeof(int) * size);
    MergeSortInner(array, 0, size, extra);
    free(extra);
}

// 非递归实现
void MergeSortNoR(int array[], int size) {
    int* extra = (int*)malloc(sizeof(int) * size);
    // 左右两个小区间的长度都是i
    for (int i = 1; i < size; i = i * 2) {
        for (int j = 0; j < size; j = j + 2 * i) {
            // 根据i和j, 确定low, mid, high
            int low = j;
            int mid = low + i;
            if (mid >= size) {
                // 没有右边的小区间，不需要合并
                continue;
            }
            int high = mid + i;
            if (high > size) {
                high = size;
            }
            Merge(array, low, mid, high, extra);
        }
    }
    free(extra);
}