输入数组,观察自底向上归并排序每一步合并后的数组状态。
归并排序:分治。自底向上时,先两两合并成长度为 2 的有序段,再合并成长度为 4 的有序段,直至整个数组有序。
合并两个有序段为 O(n),总复杂度 O(n log n),稳定排序。