【千锤百炼Python—8】：十大排序算法之归并排序

**

**

归并排序是排序算法系列的第七个要介绍的算法！

归并排序既属于比较类排序也属于内部排序。

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序的二路归并排序方式：

• 二路归并：将待排序列分成两个长度相等的子序列，然后对每个子序列进行排序，然后将排序好的子序列合并成一个完整序列。

• 步骤一：把一个待排序序列分成两个长度相等的序列；
• 步骤二：对这两个子序列分别进行归并排序；
• 步骤三：将这两个排序好的子序列合并为完整的排序序列。

import math


def mergesort(arr):
    if(len(arr) < 2):
        return arr
    middle = math.floor(len(arr) / 2)
    left, right = arr[0: middle], arr[middle:]
    return merge(mergesort(left), mergesort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

if __name__ == "__main__":
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(mergesort(arr))

输出结果为：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]