归并排序（Python实现）

原理

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
这是一种递归算法，每次将一个列表一分为二，如果列表为空或只有一个元素，那么从定义上来说它就是有序的。如果列表不止一个元素，就将列表一分为二，并对两部分都递归调用归并排序。
该算法1945年由约翰·冯·诺伊曼首次提出。

时间复杂度

归并排序是一种稳定的排序算法，时间复杂度为：O(nlogn)

# -*- coding:utf-8 -*-
# 归并排序

def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2 # 向下取整
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        lefthalf = mergeSort(lefthalf)
        righthalf = mergeSort(righthalf)

        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i = i + 1
            else:
                alist[k] = righthalf[j]
                j = j + 1
            k = k + 1

        while i < len(lefthalf):
            alist[k] = lefthalf[i]
            i = i + 1
            k = k + 1

        while j < len(righthalf):
            alist[k] = righthalf[j]
            j = j + 1
            k = k + 1
    return alist

b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
mergeSort(b)