原理

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（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)

原理

在列表较低的一端维护一个有序的子列表，并逐个将后面每个新元素“插入”这个子列表。

1. 将待排序列表的第一个元素当做已排序序列，第二个元素到最后一个元素当成未排序序列。
2. 取未排序序列中的第一个数据，插入到已排序序列中顺序正确的位置。将未排序的第一个数据与相邻的前一个数据(已排序序列的最后一个数)据进行比较，如果顺序错误则交换位置，交换位置后继续与相邻的前一个数据进行比较，直到不需要交换则插入完成。每次插入数据后，已排序序列都是排好序的。
3. 重复上一步，继续插入下一个数据。每进行一次插入，已排序序列的长度加1，未排序序列的长度减1，直到列表中的所有数据都插入到已排序序列了，则列表排序完成。

时间复杂度

插入排序的时间复杂度也是O(n²)。

Python 实现

# -*- coding: UTF-8 -*-
# 插入排序

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position = position-1

        alist[position] = currentvalue
    return alist