# 合併排序法
by: hush
---
## 概念
----
合併排序法(Merge sort)的概念是先分割再合併
----
- 分割：
就是一直對半分割下去(使用遞迴)
直到序列只剩一個元素就回傳
- 合併：
將左右兩邊排好的序列合併成一個排好的序列
將排好的序列回傳
----
----
- 程式碼講解：(live coding)
```cpp=
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int a[200005],tmp[200005];
void merge_sort(int l,int r,int a[]) //[l,r)
{
if (l==r-1) return;
int mid=l+(r-l)/2;
merge_sort(l,mid,a);
merge_sort(mid,r,a);
int lp=l,rp=mid,p=0;
while (rp<r || lp<mid)
{
if (rp==r) tmp[p]=a[lp],p++,lp++;
else if (lp==mid) tmp[p]=a[rp],p++,rp++;
else if (a[lp]<=a[rp]) tmp[p]=a[lp],p++,lp++;
else tmp[p]=a[rp],p++,rp++;
}
for (int i=l;i<r;i++) a[i]=tmp[i-l];
}
signed main()
{
//colinorz;
int n; cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
merge_sort(0,n,a);
for (int i=0;i<n;i++) cout << a[i] << " \n"[i==n-1];
}
```
----
- 複雜度分析：
每次都是對半分，可以分$log_2 n$層，合併也是$log_2 n$層，每一層雙指標會跑$n$次
- 時間複雜度$O(n log_2 n)$，最好最壞都一樣
- 額外空間複雜度$O(n)$
- 屬於穩定排序
---
## 逆序數對
----
- 定義：
在一個序列中兩個數前面的數$>$後面的數稱為一對逆序數對($i<j, a[i]>a[j]$)
- 例如：
序列$\{1, 7, 4, 5, 2\}$之中有$(7, 4), (7, 5), (7, 2), (4, 2), (5, 2)$ 5對
----
- 題目：
給定一個序列$a$ ($|a|\le 2\times 10^5$)，求$a$的逆序數對數量，或是可以任意交換相鄰兩數，求最少需要交換幾次可使序列被排序(一樣意思)
----
- 題解：
暴力枚舉時間要$O(n^2)$肯定不行。可以改良合併排序法，利用[遞迴思考](https://hackmd.io/@hush/SJQ8G6SEJe)，左右兩個子序列靠遞迴函式去算，只要再加上橫跨左右兩邊的數對數量即可
----
在合併時左右兩序列已完成排序，所以若左邊序列最小值$>$右邊序列最小值，則左邊序列剩下所有數與右邊序列最小值可組成逆序數對
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int a[200005],tmp[200005];
int ans=0;
void merge_sort(int l,int r,int a[]) //[l,r)
{
if (l==r-1) return;
int mid=l+(r-l)/2;
merge_sort(l,mid,a);
merge_sort(mid,r,a);
int lp=l,rp=mid,p=0;
while (rp<r || lp<mid)
{
if (rp==r) tmp[p]=a[lp],p++,lp++;
else if (lp==mid) tmp[p]=a[rp],p++,rp++;
else if (a[lp]<=a[rp]) tmp[p]=a[lp],p++,lp++;
else //a[lp]>a[rp]
{
tmp[p]=a[rp],p++,rp++;
ans+=mid-lp;
}
}
for (int i=l;i<r;i++) a[i]=tmp[i-l];
}
signed main()
{
//colinorz;
int n; cin >> n;
for (int i=0;i<n;i++) cin >> a[i];
merge_sort(0,n,a);
for (int i=0;i<n;i++) cout << a[i] << " \n"[i==n-1];
cout << ans << endl;
}
```
---
# 謝謝大家
{"title":"合併排序法","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":3073,\"del\":426}]","description":"by: hush"}