二路归并排序

一、概述

归并排序是分治法（Divide and Conquer）的一个非常典型的应用。它的思想就是要排序整个序列，就先把子序列排序好，然后再将有序的子序列进行合并。时间复杂度是O(nlog(n))。

二、算法图解

首先是“分”，将序列不断分成子序列

然后是“治”，即将有序的子序列合起来，最终保证整个序列是有序的

在两个有序子序列合并的时候，开辟一块辅助空间，然后将两个子序列的值合并到这个辅助空间中，在把辅助空间的值赋值回到原数组。下面是图解：

三、代码实现

#include <iostream>
#define N 1000
using namespace std;

void Merge(int a[], int left, int mid, int right)
{
    int b[right - left + 1]; // 辅助数组
    int p1 = left; // 两个指针分别指向每个子序列的开始
    int p2 = mid + 1;
    int cnt = 0;
    while (p1 <= mid && p2 <= right) 
        if (a[p1] <= a[p2]) // 小值插入
            b[cnt++] = a[p1++];
        else
            b[cnt++] = a[p2++];
    
    // 最后可能有序列还有剩余元素。
    while (p1 <= mid) 
        b[cnt++] = a[p1++];
    while (p2 <= right)
        b[cnt++] = a[p2++];
    
    // 将辅助数组的元素赋值回a数组
    for (int i = 0; i < cnt; i++)
        a[i + left] = b[i];
}

void mergesort(int a[], int left, int right)
{
    int mid = (left + right) / 2; // 求中间的下标，进行分组
    if (left == right) // 当左右边界为同一个元素的时候，代表这个分组只有一个元素，直接返回
        return;
    else
    {
        mergesort(a, left, mid); // 对左序列进行归并排序
        mergesort(a, mid + 1, right);// 对右序列进行归并排序，注意mid + 1
        Merge(a, left, mid, right); // 左右子序列合并
    }
}

int main()
{
    int a[N], n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    mergesort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}