归并排序——模板题

原题链接：

ACwing归并排序模板题

AC模板源代码：

#include <iostream>

using namespace std;

const int N = 100010;

int a[N];
int tmp[N];

void merge_sort( int a[], int l , int r)
{
    if ( l == r) return;
    int mid = l + r >> 1;

    merge_sort(a, l , mid), merge_sort( a , mid + 1, r);

    int k = 0 , i = l , j = mid + 1;
    while ( i <= mid && j <= r)
        if (a[i] < a[j] ) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];

    while ( i <= mid ) tmp[k++] = a[i++];
    while ( j <= r) tmp[k++] = a[j++];
    for ( i = l, j = 0 ; i <= r ; i ++, j ++) a[i] = tmp[j];
}

int main()
{
    int n ;
    cin >> n;
    for (int i = 0 ; i < n ; i ++) scanf("%d", &a[i]);
    merge_sort( a , 0 , n - 1);

    for (int i = 0 ; i < n ; i ++) printf("%d ",a[i]);

    return 0;
}

---

归并排序算法原理：

归并排序GIF演示

归并排序思路

---

相关代码解析：

---

附注：

i++与++i的区别

i++是先赋值，然后再自增；++i是先自增，后赋值。
用代码表示就是：
若 a = i++;则等价于a=i;i=i+1;
而a = ++i;则等价于 i=i+1;a=i;

---

参考资料：

1. YXC讲解视频
2. i++与++i区别