单点时限: 5.0 sec
内存限制: 512 MB
自然合并排序是合并排序算法的一种改进, 对于初始给定的数组, 通常存在多个长度大于1的已自然排好序的子数组段。
例如, 若数组$a$中元素为$(1, 5, 2, 3, 6, 0, 7, 4, 8,9,10)$, 则自然排好序的子数组段有$((1, 5), (2, 3, 6), (0, 7), (4, 8),(9,10))$。
然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段$((1, 2, 3, 5, 6), (0, 4, 7, 8),(9,10))$。
继续合并相邻排好序的子数组段$((0,1,2,3,4,5,6,7,8),(9,10))$。
最后合并为$((0,1,2,3,4,5,6,7,8,9,10))$
输入共两行
第一行一个整数$n(n\leqslant10^6)$表示数字序列的长度
第二行$n$个整数表示需要排序的序列
每次将相邻的排好序的子数组段两两合并之后,输出一行整数,以空格分割,表示当前的序列顺序,直到排序结束。
10 67 77 82 74 83 23 58 58 93 86
67 74 77 82 83 23 58 58 86 93 23 58 58 67 74 77 82 83 86 93
10 21 39 58 69 98 64 28 84 78 57
21 39 58 64 69 98 28 78 84 57 21 28 39 58 64 69 78 84 98 57 21 28 39 57 58 64 69 78 84 98
当子数组的个数是奇数时,先不合并最后一个子数组。
仅在每轮合并过后输出,如果数组原来就是有序的,你不需要输出任何信息。