归并排序

给定你一个长度为 n 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

归并排序的思想是分治，先将数组一分为二，分为[l,mid]和[mid+1,r]重复这个操作直到分为只有一个元素，即l==r时return。

数组两两合并，由于是从只有一个元素开始返回，所以保证每次都是两个有序数组合并。

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
#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N];
int t[N];
void merge(int l,int r){
    if(l==r) return;
    int mid=l+r>>1,i=l,j=mid+1,k=0;
    merge(l,mid);
    merge(mid+1,r);
    while(i<=mid&&j<=r){
        if(a[i]<a[j]) t[k++]=a[i++];
        else t[k++]=a[j++];
    }
    while(i<=mid) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];
    for(i=l,k=0;i<=r;i++,k++) a[i]=t[k];
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    merge(0,n-1);
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    return 0;
}