算法：归并排序

归并排序----分治
时间复杂度：O(n) = nlogn
稳定性：稳定的排序算法
步骤：
第一步：确定分界点：mid = (l + r) / 2
第二步：归并排序left，right
第三步：归并合二为一
代码：

#include<iostream>
using namespace std;
int a[100010];
int n;
int temp[100010];
void merge_sort(int l, int r){
    if(l >= r){
        return;
    }
    int mid = (l + r) >> 1;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
    int j = mid + 1;
    int i = l;
    int k = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];
    for(int i = l, j = 0; i <= r; ++i, ++j) a[i] = temp[j];
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; ++i){
        scanf("%d", &a[i]);
    }
    merge_sort(0, n-1);
    for(int i = 0; i < n; ++i){
        printf("%d ", a[i]);
    }
    return 0;
}

注意：

将temp中的值放回原数组中时，需要利用i,j两个变量进行，因为i从l到r，j从0开始。这样就能将原数组中的l到r排好序。