归并排序，分为两个步骤：
第一个步骤是“分”，将需排序的数组进行2路划分，直到划分为一个个有序的子数组，然后进行两两合并。
第二个步骤就是“治”，也就是进行合并，合并过程为对两个子数组的每一个元素进行比较，较小的元素在前，
直到遍历完两个子数组。
2-路合并
def merge(arr, low, mid, high):
arr_copy = arr[:]
i, j = low, mid + 1
k = i
while i <= mid and j <= high:
if arr_copy[i] <= arr_copy[j]:
arr[k] = arr_copy[i]
i += 1
else:
arr[k] = arr_copy[j]
j += 1
k += 1
while i <= mid:
arr[k] = arr_copy[i]
k += 1
i += 1
while j <= high:
arr[k] = arr_copy[j]
k += 1
j += 1
2-路归并 -- 递归
递归较为容易理解，就是上述的不断划分，然后合并
def mergeSort(arr, low, high):
if low < high:
mid = (low + high) // 2
mergeSort(arr, low, mid)
mergeSort(arr, mid + 1, high)
merge(arr, low, mid, high)
2-路归并 -- 迭代
迭代相对于递归较为麻烦，需要我们确定每两个需要合并的子数组的起始位置，中间分割位置以及结束位置，然后循环进行两两合并
这里增加了一个步长，即划分的子数组的长度，从1开始，依次为2，4，8，16,...,当>= 原数组长度时结束。
def mergeSort_iteration(arr, high):
length = 1 # 步长
while length < high:
i = 0
while i + 2 * length < high: # 进行两两合并
merge(arr, i, i + length - 1, i + 2 * length - 1)
i = 2 * length
if i + length < high: # 针对划分为奇数个子数组的情况，最后一个子数组单独出来了，需要额外处理
merge(arr, i, i + length - 1, high)
length *= 2
测试
if __name__ == "__main__":
arr = [3,2,1,5,4]
# mergeSort(arr, 0, 4)
mergeSort_iteration(arr, 4)
print(arr)
