归并排序

归并排序 · Merge Sort，是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法 · Divide and Conquer 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并操作

归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如：设有数列 { 6, 202, 100, 301, 38, 8, 1 }

初始状态：6, 202, 100, 301, 38, 8, 1

第一次归并后：{ 6, 202 }, { 100, 301 }, { 8, 38 }, { 1 }，比较次数：3；

第二次归并后：{ 6, 100, 202, 301 }, { 1, 8, 38 }，比较次数：4；

第三次归并后：{ 1, 6, 8, 38, 100, 202, 301 }，比较次数：4；

总的比较次数为：3 + 4 + 4 = 11；

逆序数为 14；

算法描述

归并操作的工作原理如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤 3 直到某一指针超出序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

逆序对

设 A 为一个有 $n(n \ > \ 1)$ 个数字的有序集，其中所有数字各不相同。

如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则（A[i], A[j]）这个有序对称为 A 的一个逆序对，也称作逆序数。

模板

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;

int n, a[100005], tmpA[100005], cnt;
 
void merge_sort(int l, int r, int *A)
{
    if (l >= r) return ;
    int mid = (l + r) >> 1;
    merge_sort(l, mid, A);
    merge_sort(mid + 1, r, A);
    int pl = l, pr = mid + 1, tmpp = 0;
    while(pl <= mid && pr <= r)
    {
        if (A[pl] <= A[pr]) tmpA[tmpp++] = A[pl++];
        else tmpA[tmpp++] = A[pr++], cnt += mid - pl + 1;
    }
    while(pl <= mid) tmpA[tmpp++] = A[pl++];
    while(pr <= r) tmpA[tmpp++] = A[pr++];
    for (int i = 0; i < tmpp; i++) A[i + l] = tmpA[i];
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    merge_sort(1, n, a);
    printf("%d\n", cnt);    //cnt：逆序对个数
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}