AcWing
787. 归并排序
归并排序。
void merge_sort(int a[], int l, int r): 对数组a的l~r的范围中的元素进行排序，也就是对a[l~r]进行归并排序。
- 边界处理：当
l>=r的时候，说明l~r这个范围内只有一个元素或没有元素。一个元素的数组，是有序的，递归结束； - 如果
l<r,则进行归并排序； - 首先寻找
l~r的中点int mid = l+r >> 1； - 对左半边进行归并排序，对右半边进行归并排序；
- 当左右半边都排好序后，需要合并左右半边数组，到一个临时数组
tmp[N]中，合并数组用的是双指针法； - 然后将临时数组
tmp[N]中的数，拷贝回原数组的对应位置，排序结束。
算法的时间复杂度是$O(nlogn)$.
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int a[N], tmp[N];
void mergesort(int l, int r){
if(l >= r) return;
int mid = l + r >> 1;
mergesort(l, mid);
mergesort(mid + 1, r);
int pt1 = l, pt2 = mid + 1, pt3 = 1;
while(pt1 <= mid && pt2 <= r){
if(a[pt1] <= a[pt2]) tmp[pt3++] = a[pt1++];
else tmp[pt3++] = a[pt2++];
}
while(pt1 <= mid) tmp[pt3++] = a[pt1++];
while(pt2 <= r) tmp[pt3++] = a[pt2++];
for(int i = l, j = 1; i <= r; i ++, j ++) a[i] = tmp[j];
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
mergesort(1, n);
for(int i = 1; i <= n; i ++) cout << a[i] << " \n"[i == n];
return 0;
}