归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
代码实现：
def merge_sort(alist): n = len(alist) if n <= 1: return alist mid = n//2 left_li = merge_sort(alist[:mid]) #采用归并排序后形成的新的列表（左边的） right_li = merge_sort(alist[mid:]) #采用归并排序后形成的新的列表（右边的） #将两个有序的子序列合并成一个新的有序整体 left_pointer,right_pointer = 0,0 #左边和右边序列的游标 result = [] while left_pointer < len(left_li) and right_pointer < len(right_li): if left_li[left_pointer] <= right_li[right_pointer]: result.append(left_li[left_pointer]) left_pointer += 1 else: result.append(right_li[right_pointer]) right_pointer += 1 result += left_li[left_pointer:] result += right_li[right_pointer:] return result if __name__ == "__main__": li = [55,66,84,22,46,31] print(li) sorted_li = merge_sort(li) print(li) print(sorted_li)
代码分析 ：
时间复杂度：
稳定性：（稳定）
原文：https://www.cnblogs.com/fenglivoong/p/12704410.html