归并排序

def mergeSort(alist):
    if len(alist) > 1:
        #基本结束条件，当len=1时，直接不走if内的模块，直接return 
        mid = len(alist) // 2
        leftlist = alist[:mid]
        rightlist = alist[mid:]
        mergeSort(leftlist)
        mergeSort(rightlist)
        i = j = k = 0 
        while i < len(leftlist) and j < len(rightlist):
            if leftlist[i] < rightlist[j]:
                alist[k] = leftlist[i]
                i += 1 
            else:
                alist[k] = rightlist[j]
                alist[k] = rightlist[j]
                j += 1 
            k += 1 
        while i < len(leftlist):
            alist[k] = leftlist[i]
            i += 1
            k += 1 
        while j < len(rightlist):
            alist[k] = rightlist[j]
            j += 1 
            k += 1 
    return alist 

书上说：

最后， 我们还是注意到两个切片操作为了时间复杂度分析精确起见，可以通过取消切片操作，改为传递两个分裂部分的起始点和终止点，也是没问题的，只是算法可读性稍微牺牲一点点。

请问 改为传递两个分裂部分的起始点和终止点的代码怎么写

1.将整个数组对半分开，直到只剩一个元素

2.从一个元素开始往回进行对比合并，将合并的内容暂且放在一个空列表中

定义合并merge函数

def merge(L,R):
# 将两个排过序的两个列表进行合并并排序
# 分别用于限定L、R的数据减少情况
i, j = 0,0
# 用于存放L与R的合并内容
res = []
while i < len(L) and j < len(R):
# 如果左边的数大于右边的数，就将左边的数先添加到res中，再继续比较（合并的R、L已经排过序）
# 如果如果右边的数大于左边的数，就将右边的数先添加到res中，再继续比较（合并的R、L已经排过序）
if L[i] <= R[j]:
res.append(L[i])
i += 1
else:
res.append(R[j])
j += 1
# 因为当 i == len(L) 或者 j == len(R)时，跳出while循环，且每次循环只处理一个列表里的内容，所以其中有一个列表内容会先全部加入res中，另一个列表还剩内容未加进res中。
# 对未处理完的列表，直接加入res中
res += R[j:] if i == len(L) else L[i:]
return res

定义排序merge_sort函数

def merge_sort(List):
length = len(List)
if length <= 1:
return List
else:
mid = length//2
left = merge_sort(List[:mid])
right = merge_sort(List[mid:])
return merge(left,right)

if name == 'main':
List = [9,8,7,5,3,6,11,2,4,1,12]
print(merge_sort(List))

list.pop(0)弹出第一个元素并且必须移动所有剩余的元素，这是一个额外的 O(n) 操作

def fastmerge(array1,array2):
    merged_array=[]
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop())
        elif (not array2) or array1[-1] > array2[-1]:
            merged_array.append(array1.pop())
        else:
            merged_array.append(array2.pop())
    merged_array.reverse()
    return merged_array

def fastmergeSort(array):
    n  = len(array)
    if n <= 1:
        return array
    left = array[:n//2]
    right = array[n//2:]
    return fastmerge(fastmergeSort(left),fastmergeSort(right))

print(fastmergeSort([9,8,7,6,5,4,3,2,1]))

将整个数组对半分开，直到只剩一个元素

def merge_sort(lst):
    # 递归结束条件
    if len(lst) <= 1:
        return lst

    # 分解问题，并递归调用
    middle = len(lst) // 2
    left = merge_sort(lst[:middle]) # 左半部排好序
    right = merge_sort(lst[middle:]) # 右半部排好序

    # 合并左右半部，完成排序
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    merged.extend(right if right else left)
    return merged