2.2.29 #

解答 #

完全有序时只需要一次归并（直接输出），

逆序时需要 n - 1 次归并（退化为插入排序），

平均需要 n/2 次归并。

所以分别需要 500，500000，500000000 次归并。