#include<iostream>
#include<fstream>
#include<stack>
using namespace std;
enum node_type { LEFT, RIGHT};
class stack_node{
private:
int first, last;
node_type type;
int level;
public:
stack_node(int _first, int _last, node_type _type, int _level): first(_first), last(_last), type(_type), level(_level){};
~stack_node(){};
stack_node* divide(node_type _type);
bool sizeOne();
node_type typ();
int getFirst(){return first;};
int getLast(){return last;};
int getLevel(){return level;};
};
node_type stack_node::typ(){
return type;
}
stack_node* stack_node::divide(node_type _type){
if(first == last)
return NULL;
stack_node* tmp;
if(_type == LEFT)
tmp = new stack_node(first, first + ((last - first) / 2), LEFT, level+1);
else
tmp = new stack_node(first + ((last - first) / 2) + 1, last, RIGHT, level+1);
return tmp;
}
bool stack_node::sizeOne(){
if(first == last)
return true;
return false;
}
class non_recursive_merge{
private:
stack<stack_node*> sorted_stack;
stack<stack_node*> unsorted_stack;
int* arr;
int size;
public:
non_recursive_merge(int* _arr, int _size):arr(_arr), size(_size){};
~non_recursive_merge(){};
void merge();
stack_node* merge_sort(stack_node* left, stack_node* right);
void show();
};
void non_recursive_merge::show(){
for(int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
stack_node* non_recursive_merge::merge_sort(stack_node* left, stack_node* right){
int size = (right->getLast() - left->getFirst()) + 1;
int* tmp = (int*)malloc(sizeof(int) * size);
int i;
int lefti = left->getFirst();
int righti = right->getFirst();
for(i = 0; i < size; i++){
if(arr[lefti] < arr[righti])
tmp[i] = arr[lefti++];
else
tmp[i] = arr[righti++];
if(lefti == left->getLast()+1 || righti == right->getLast()+1)
break;
}
if(righti == right->getLast()+1)
for(i++; i < size; i++)
tmp[i] = arr[lefti++];
else if(lefti == left->getLast()+1)
for(i++ ; i < size; i++)
tmp[i] = arr[righti++];
lefti = left->getFirst();
for(i = 0; i < size; i++){
arr[lefti] = tmp[i];
lefti++;
}
lefti = left->getFirst();
righti = right->getLast();
int level = left->getLevel();
delete left;
delete right;
return new stack_node(lefti, righti, LEFT, level-1);
}
void non_recursive_merge::merge(){
stack_node* init = new stack_node(0, size-1, LEFT, 0);
unsorted_stack.push(init);
while(true){
if(unsorted_stack.empty())
break;
stack_node* tmp = unsorted_stack.top();
unsorted_stack.pop();
if(tmp->sizeOne()){
if(tmp->typ() == LEFT)
sorted_stack.push(tmp);
else{
while(!sorted_stack.empty()){
stack_node* aleady_sorted = sorted_stack.top();
if(aleady_sorted->getLevel() != tmp->getLevel())
break;
sorted_stack.pop();
tmp = merge_sort(aleady_sorted, tmp);
}
sorted_stack.push(tmp);
}
}
else{
unsorted_stack.push(tmp->divide(RIGHT));
unsorted_stack.push(tmp->divide(LEFT));
delete tmp;
}
}
}
int main(){
ifstream fin = ifstream("input.txt");
int testcase, testcase_cnt;
fin >> testcase;
for(testcase_cnt = 0; testcase_cnt < testcase; testcase_cnt++){
int num_cnt;
fin >> num_cnt;
int* num = (int*)malloc(sizeof(int) * num_cnt);
for(int i = 0; i < num_cnt; i++)
fin >> num[i];
non_recursive_merge m(num, num_cnt);
m.merge();
m.show();
}
return 0;
}