介绍一种新的排序算法，归并排序。 总的来说，前面介绍了两种排序算法，冒泡排序（选择排序）和插入排序（希尔排序）。冒泡排序是依次两两对比，选取较大的进行比较，时间复杂度均为O(n2)；插入排序是依次选取一个元素，将其插入到排好序的有序表中（类似于有序链表的插入操作）。插入排序的是按复杂度也是O(n2）。希尔排序在选择最优的间隔序列后，时间复杂度为O(n^(3/2)) 归并排序是一种基于分治策略的排序算法。将总的待排序列分成若干个小的子序列，然后分别对其进行排序。排完序后对子序列逐步进行归并。
思路：归并排序采用递归的形式，每次将当前序列分为两部分，递归，直到每个子序列只有一个元素，这样每个子序列其实就是有序的了，然后递归返回，接下来就是归并的过程了，想一想如何将留两个有序的序列合并为一个有序的序列？（可以看出来，归并排序的主要过程其实就是归并的过程）
没错，就是各自从前往后遍历比较，（默认是从小到大排列，升序）比如取出A序列的第一个元素，取出B序列的第一个元素，如果A中第一个元素小于B中的第一个元素。那么将A中的第一个元素加入到新的有序序列中，取出A中的第二个元素，与B中的第一个元素进行比较，哪个小就把他加入新的有序序列，并取出该序列的下一个元素，以此类推。直到有一个序列遍历完，那么 剩下的那个部分序列就直接原封不动加入到新的序列中就好了（因为本来就是有序的）。
这是教程给的代码1
# 归并排序1 def merge_sort(alist): if len(alist) > 1: mid = len(alist) // 2 left_half = alist[:mid] right_half = alist[mid:] merge_sort(left_half) merge_sort(right_half) i = 0 j = 0 k = 0 while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]: alist[k] = left_half[i] i = i + 1 else: alist[k] = right_half[j] j = j + 1 k = k + 1 while i < len(left_half): alist[k] = left_half[i] i = i + 1 k = k + 1 while j < len(right_half): alist[k] = right_half[j] j = j + 1 k = k + 1 alist = [2,7,5,84,10,1,3,9,8,6] # alist = [2,1,1,1,1,1,1,1,1] merge_sort(alist) print(alist)这是教程给的代码2，比较Python化，充分利用了Python的语法以及便捷性
# 归并排序2 def merge_sort(alist): if len(alist) <= 1: return alist middle = len(alist) // 2 left = merge_sort(alist[:middle]) right = merge_sort(alist[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 alist = [2,7,5,84,10,1,3,9,8,6] # alist = [2,1,1,1,1,1,1,1,1] print(merge_sort(alist))这是我自己写的（其实是看了教程给的代码后才写出来的┭┮﹏┭┮）。因为本来之前是用C学的算法课，所以对Python还是一时转不过弯来。
# 归并排序 def merge_sort(alist): # 这是递归终止条件，还是用<=比较好，否则如果传过来是一个空列表就会报错 if len(alist) <= 1: return alist else: # 分割序列 left = alist[:len(alist) // 2] right = alist[len(alist) // 2:] # 分别排序 left_list = merge_sort(left) right_list = merge_sort(right) # 归并两个子序列 i = 0 j = 0 k = 0 new_list = [] while i < len(left_list) and j < len(right_list): if left_list[i] <= right_list[j]: new_list.append(left_list[i]) i += 1 else: new_list.append(right_list[j]) j += 1 while i < len(left_list): new_list.append(left_list[i]) i += 1 while j < len(right_list): new_list.append(right_list[j]) j += 1 return new_list alist = [2,7,5,84,10,1,3,9,8,6] # alist = [2,1,1,1,1,1,1,1,1] print(merge_sort(alist))时间复杂度为O(nlogn)。可以看成是两个部分，一个是分裂，一个是归并。分裂的时间复杂度和二分查找的类似，就是直到每个序列剩余一个时就终止，即n/(2^i)=1，i为logn。归并的过程其实在数量级上来说就是两两对比了，O(n)的时间复杂度。因为整个过程是分裂后再归并，即每次分裂都对应着一次归并。所以时间复杂度为O(nlogn)。
