归并排序的时间复杂度O（nlogn），空间复杂度为O（n）
首先我们先假设有两个有序数组，我们去进行一次归并
用代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | def merge(li: list, start: int, mid: int, end: int) : res=[] j = mid +1 while start <= mid and j <= end: if li[start] < li[j]: res.append(li[start]) start +=1 else: res.append(li[j]) j +=1 #运行到这一步，说明左右两边一定有一遍已经下标已经超了，即一定有一遍数字已经没了 #然后判断如果是左边还有数字就把左边剩下的数字全部插入列表中，无需在做判断 #判断如果是右边还有数字就把左边剩下的数字全部插入列表中，无需在做判断 while start <= mid: res.append(li[start]) start +=1 while j <= end: res.append(li[j]) j +=1 li[start:end+1] = res return res |
最后交给递归