Title Description

Merging sorting is an O(nlogn) algorithm, which is much better than bubbling sorting and inserting sorting for a large number of data.

This is a sorting exercise with a large amount of data. Please use merge sorting to finish it.

 

input

The number n in the first line represents the number of input groups

Then enter a number m in the first row of each group to represent the number of numbers to be sorted

After that, there is one data in each row of m rows, the size is between 1 and 100000, which is not equal to each other, with a maximum of 100000 data.

output

Ascending output ordered data, one digit per line

sample input

1
10
10
9
8
7
6
5
4
3
2
1

sample output

1
2
3
4
5
6
7
8
9
10

#include<bits/stdc++.h>
using namespace std;

void Merge(vector<int>&res, int L1, int R1, int L2, int R2)
{
    vector<int>ans(R2-L1+10);
    int i = L1, j=L2, index=0;
    while(i<=R1 && j<=R2)
    {
        if(res[i]<res[j])
            ans[index++] = res[i++];
        else
            ans[index++] = res[j++];

    }
    if(i<=R1)
    {
        while(i<=R1)
            ans[index++] = res[i++];
    }
    if(j<=R2)
    {
        while(j<=R2)
            ans[index++] = res[j++];
    }
    index = 0;
    for(int i=L1; i<=R2; ++i)
        res[i] = ans[index++];
}


void mergesort(vector<int>&res, int i, int j)
{
    if(i < j)
    {
        int pos = (j-i)/2+i;
        mergesort(res, i, pos);
        mergesort(res, pos+1, j);
        Merge(res, i, pos, pos+1,j);
    }
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int m;
        cin >> m;
        vector<int>res(m);
        for(int i=0; i<m; ++i)
            cin >> res[i];
        mergesort(res, 0, res.size()-1);
        for(int i=0; i<m; ++i)
        {
            cout << res[i];
            if(i==n-1)
                continue;
            else
                cout<<endl;
        }
    }

    return 0;

}