归并排序(Merge sort)主要思想是分治法(divide and conquer)，就是要将n个元素的序列划分为两个序列，再将两个序列划分为4个序列，直到每个序列只有一个元素，最后，再将两个有序序列归并成一个有序的序列。
- Code
"""
Merge Sort
"""
def merge(left_array, right_array):
"""
对数组left_array和right_array进行归并
"""
temp_array = [] # 新的已排序好的临时列表
left_index = 0 # left_array列表的下标
right_index = 0 # right_array列表的下标
while left_index < len(left_array) and right_index < len(right_array):
"""
对两个列表中的元素 两两对比，将最小的元素，放到result中，并对当前列表下标加1
"""
if left_array[left_index] <= right_array[right_index]: # 如果左边的值小于等于右边的值
temp_array.append(left_array[left_index]) # 临时数组加入左边的值
left_index += 1 # left_array数组的下标+1
else:
temp_array.append(right_array[right_index]) # 临时数组加入右边的值
right_index += 1 # right_array数组的下标+1
temp_array += left_array[left_index:]
temp_array += right_array[right_index:]
return temp_array
def merge_sort(array):
"""
对数组array进行拆分
"""
if len(array) <= 1: # 如果数组的元素少于或只有一个
return array # 直接把数组返回
middle = int(len(array) / 2) # 把数组进行拆分
left_array = merge_sort(array[:middle]) # 左边的数组
right_array = merge_sort(array[middle:]) # 右边的数组
return merge(left_array, right_array) # 对排序好的两个列表合并，产生一个新的排序好的列表
print(merge_sort([8, 6, 2, 3, 1, 5, 7, 4]))
- Output
[1, 2, 3, 4, 5, 6, 7, 8]
