题目描述

归并排序采用各个击破的思路。例如一个长度为8个数的数组，原始序列如下：8,4,7,5,3,1,6,2 我们可以每次二分，直到区间划分成1个，那么肯定是有序的。然后回撤去排长度为2的区间，例如(8,4)(7,5)(3,1)(6,2) 排序后应该为(4,8)(5,7)(1,3)(2,6),以此类推，对长度为4的区间进行有序合并，最后得到(4,5,7,8)(1,2,3,6) 最后对2个长度为4的区间再次合并，可以得到最终的序列 由于归并排序需要先二分，再合并，根据递归程序的特点，一般只有前半段全部处理完毕，再处理后半段。为了方便判题 我们简化输出，每次二分合并后就打印出当前处理的区间和当前最新的数组信息，例如： low=0,mid=0,high=1 [4, 8, 7, 5, 3, 1, 6, 2] low=2,mid=2,high=3 [4, 8, 5, 7, 3, 1, 6, 2] low=0,mid=1,high=3 [4, 5, 7, 8, 3, 1, 6, 2] low=4,mid=4,high=5 [4, 5, 7, 8, 1, 3, 6, 2] low=6,mid=6,high=7 [4, 5, 7, 8, 1, 3, 2, 6] low=4,mid=5,high=7 [4, 5, 7, 8, 1, 2, 3, 6] low=0,mid=3,high=7 [1, 2, 3, 4, 5, 6, 7, 8] ans[1, 2, 3, 4, 5, 6, 7, 8]

输入格式

若干组测试数据，每行第一个数组m表示待排序的个数，接下来m个整数表示数组的每一个元素

输出格式

按题目要求输出归并排序每一次划分合并后的排序效果。为了方便编程，数组直接使用Arrays.toString(）打印。（仅限java语言，其他语言自己实现） 每组测试数据之间用一个空行隔开

9
67 65 77 68 97 3 33 49 34

low=0,mid=0,high=1	[65, 67, 77, 68, 97, 3, 33, 49, 34]
low=0,mid=1,high=2	[65, 67, 77, 68, 97, 3, 33, 49, 34]
low=3,mid=3,high=4	[65, 67, 77, 68, 97, 3, 33, 49, 34]
low=0,mid=2,high=4	[65, 67, 68, 77, 97, 3, 33, 49, 34]
low=5,mid=5,high=6	[65, 67, 68, 77, 97, 3, 33, 49, 34]
low=7,mid=7,high=8	[65, 67, 68, 77, 97, 3, 33, 34, 49]
low=5,mid=6,high=8	[65, 67, 68, 77, 97, 3, 33, 34, 49]
low=0,mid=4,high=8	[3, 33, 34, 49, 65, 67, 68, 77, 97]
ans[3, 33, 34, 49, 65, 67, 68, 77, 97]