Sort in Group

Luogu. P1177
To ReadNOutput after child to large

Input Format

The first act is a positive integer.N。
OrganisationNPositive integer number of spaces separateda_I , the number you need to sort.

Output Format

To be givenNNumbers range from small to large output, with spaces separated between numbers, line ends and no spaces.

For 20% of the data, there's one.N≤10³;

For 100% of the data, there's one.N≤10⁵ One._I≤10⁹。

Example

输入
5
5 2 4 5 1

输出
1 2 4 4 5

Grouping Main UseThe idea of partition., time complex is O (I don't know.)。

int n, a[100010], b[100010];    /* 此处a，b为辅助数组 */

void merge_sort(int q[], int l, int r){
    if(l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);  /* 递归拆分 */

    int i = l, j = mid + 1, k = l;  /* 合并 */
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    }

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

Here's the idea.

1. The array continues for an equal length.SplitUntilOne count.length;
2. Backtrace, in ascending orderMergeTwo left and right.
3. Repeat the above two processes until the end of the regression.

Division

合并：
1. i,j 分别指向a的左右段起点，k指向b的起点。
2. 枚举a数组，如果左数≤右数，把左数放入b数组，否则，把右数放入b数组。
3. 把左段或右端剩余的数放入b数组。
4. 把b数组的当前段复制回a数组。

Complete as follows:

#include <iostream>
using namespace std;
int n, a[100010], b[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 i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r)
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];

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

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;
}