二路归并

const int maxn = 100;
void merge(int a[], int l1, int r1, int l2, int r2) {
    int i = l1, j = l2;
    int temp[maxn], index = 0;

    //归并到temp数组
    while (i < r1 && j < r2) {
        if (a[i] <= a[j]) {
            temp[index++] = a[i++];
        }
        else {
            temp[index++] = a[j++];
        }
    }
    while (i <= r1) temp[index++] = a[i++];
    while (j <= r2) temp[index++] = a[j++];

    //将合并的数组回归原来
    for (int i = 0;i < index;i++) {
        a[l1 + i] = temp[i];
    }
}

void mergesort(int a[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergesort(a, left, mid);
        mergesort(a, mid + 1,right);
        merge(a, left, mid, mid + 1, right);
    }
}

迭代写法,不难记，如果用sort的话，但是用merge就很难记忆了
记忆：两层循环，加最里面merge或者sort函数

const int maxn = 100;
void merge(int a[], int l1, int r1, int l2, int r2) {
    int i = l1, j = l2;
    int temp[maxn], index = 0;

    //归并到temp数组
    while (i < r1 && j < r2) {
        if (a[i] <= a[j]) {
            temp[index++] = a[i++];
        }
        else {
            temp[index++] = a[j++];
        }
    }
    while (i <= r1) temp[index++] = a[i++];
    while (j <= r2) temp[index++] = a[j++];

    //将合并的数组回归原来
    for (int i = 0;i < index;i++) {
        a[l1 + i] = temp[i];
    }
}

（用sort比较好记忆）
void mergesort(int a[], int left, int right) {
    //step为组内元素个数，step / 2为左子区间元素个数，注意等号可以不去
    for (int i = 2;step / 2 <= n;step * 2) {
        //每step个元素一组，组内前step / 2和后step / 2元素进行合并
        for (int i = 1;i <= n;i += step) {
            int mid = i + step / 2 - 1; //左子区间元素个数为step / 2
            if (mid + 1 <= n) {  //右区间存在元素则合并
                //左子区间为[i,mid],右子区间为[mid + 1,min(i + step - 1,n)
                merge(a, i, mid, mid + 1, min(i + step - 1, n));
            }
        }
    }
}