Algorithm - Basic - Merge Sort

归并排序是一种分治排序算法,还可用于求逆序对.

思想

已知一个数组aa,对于区间[l,r][l, r],我们采取操作 MERGE(a,l,r)\mathrm{MERGE}(a, l, r)

  1. m(l+r)/2m\leftarrow (l + r) / 2.
  2. MERGE(a,l,m)\mathrm{MERGE}(a, l, m).
  3. MERGE(a,m+1,r)\mathrm{MERGE}(a, m + 1, r).
  4. 合并,拷回原数组 aa.

可视化算法请看 VisuAlgo Sorting.

复杂度分析

根据思想,我们可有递推式 T(n)=2T(n2)+O(n)T(n) = 2T(\frac{n}{2}) + \mathcal{O}(n).
根据主定理,其时间复杂度为 O(nlogn)\mathcal{O}(n\log n).
由于合并需要外部空间,其空间复杂度为 O(n)\mathcal{O}(n).

实现思路

采用递归的方式,参数为数组 aa,区间左端 ll,区间右端 rr.
显然在 lrl \geqslant r 时不需要进行排序,将其作为递归边界.
mm 为区间中点 (l+r)/2(l + r) / 2,并对左半部分排序,右半部分排序.
实现的重点实际上是合并左半部分和右半部分,并拷回原数组 aa.

假定数组 aa[l,m][l, m][m+1,l][m + 1, l] 区间已完成排序,如图所示,它们的合并更像是两个栈出栈的过程.
分别用 liliriri 表示左半部分栈顶元素下标和右半部分栈顶元素下标,初始时 lilli \leftarrow lrim+1ri \leftarrow m + 1.
接下来分为两种情况出栈

  1. 选择 a[li]a[li]a[ri]a[ri] 中较小的出栈至外部空间 bufbuf,并相应使下标自增
  2. 一个栈已空,则只对另一个栈进行出栈即可

反复进行上述两个操作之一,直到两个栈为空即 li>mli > mri>rri > r (或使用计数器 cnt\mathrm{cnt} 统计已出栈的个数,并将 cnt==(rl+1)\mathrm{cnt == (r - l + 1)} 作为终止条件)时.
再将 bufbuf[l,r][l, r] 区间拷回原数组 aa 中.
合并

逆序对

逆序对的计算发生在合并的过程中,由于两部分已经有序,在左半部分和右半部分分别出栈时,可以保证当前出栈的元素一定是小于另一个栈剩下所有元素的.
因此当右半部分出栈时,出栈的元素小于剩余的左半部分的所有元素,而此时左半部分剩余元素个数为 mli+1m - li + 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define MAXN (50000+5)
long long pairs = 0;
int buf[MAXN];
void mergesort(int *a, int l, int r)
{
if(l >= r) return;
int m = (l + r) / 2;
int cnt = 0;
int li = l;
int ri = m + 1;
mergesort(a, l, m);
mergesort(a, m + 1, r);
while(cnt != (r - l + 1))
{
// if((ri > r) || (li <= m && (a[li] >= a[ri])))
if((ri > r) || (li <= m && (a[li] <= a[ri])))
{
buf[l + cnt] = a[li];
li++;
cnt++;
}
else
{
buf[l + cnt] = a[ri];
ri++;
cnt++;
pairs += m - li + 1;
}
}
for(int i = l; i <= r; i++)
{
a[i] = buf[i];
}
}