给定一组数（42，15，20，6，8，38，50，12），我们执行归并排序的过程，如图所示。 

从图中可以看出，首先将待排序元素分成大小 大致相同的两个子序列，然后再把子序列分成大小 大致相同的两个子序列，如此下去，直到分解成一 个元素停止，这时含有一个元素的子序列必然是有序的。然后执行合并操作，将两个有序的子序列合并为一个有序序列，如此下去，直到所有的元素都合 并为一个有序序列。 

合久必分，分久必合！归并排序就是这个策略。

测试数据有多组，第1行输入测试数据的组数T。

每组测试数据包括2行，第1行输入要排序的元素个数 n（n <= 10000）。

第2行输入n个数，用空格分隔。 

输出归并排序后的结果。