分治思想

确定中间为分界点

mid = (l+r)>>1

递归排序左右两端

归并，合二为一

双指针法，比较当前所指数大小，小的填入临时数组，相应的指针前进

模板

void merge_sort(int q[], int l, int r) {
	int temp[10000];
    if (l >= r) return;

    int mid = l + r >> 1;

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

    int k = 0, i = l, j = mid + 1;


    while (i <= mid && j <= r) {
        if (q[i] < q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }

    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22