MergeInLimitedSpace

#include <iostream>
#include <algorithm>
#include <tuple>
#include <utility>
#include <random>

using namespace std;

void merge(vector<int> &input, int s) {
    vector<int> tmp;

    if (s < input.size() - s) {
        tmp.resize(s);
        move(input.begin(), input.begin() + s, tmp.begin());
    } else {
        tmp.resize(input.size() - s);
        move(input.begin() + s, input.end(), tmp.begin());
        move_backward(input.begin(), input.begin() + s, input.end());
        s = input.size() - s;
    }

    auto it1 = tmp.begin();
    auto it2 = input.begin() + s;
    for (auto it3 = input.begin(); it2 != input.end() || it1 != tmp.end(); ++it3) {
        if (it1 != tmp.end() && (it2 == input.end() || *it1 <= *it2)) {
            *it3 = *it1;
            ++it1;
        } else {
            *it3 = *it2;
            ++it2;
        }
    }
}

void solve() {
    int n;
    cin >> n;

    random_device rd;
    default_random_engine gen(rd());
    uniform_int_distribution<> dist(1, n);
    vector<int> input(n);
    for (int & elem: input) {
        elem = dist(gen);
    }
    int s = dist(gen);
    sort(input.begin(), input.begin() + s);
    sort(input.begin() + s, input.end());
    auto print_input = [&]() {
        for (int elem: input) {
            cout << elem << " ";
        }
        cout << endl;
    };
    print_input();
    merge(input, s);
    print_input();
}

int main() {
    int z;
    cin >> z;
    while (z--) solve();
    return 0;
}