第三章：高级排序算法

归并排序算法（mergeSort）

算法思想：
Python使用函数实现：

def __merge(arrList, l, mid, r):
    # 将arr[l...mid]和arr[mid + 1...r]两部分进行归并

    # 一段辅助的临时空间，大小为r-l+1
    aux = [None]*(r-l+1)
    # 将当前要处理的arrList中的元素复制到aux中
    for i in range(l, r+1):
        # aux从0开始，要处理的元素从l开始，中间有个l的偏移量。
        aux[i-l] = arrList[i]

    # 两个指针
    i = l
    j = mid + 1
    # 寻找arrList[k]处的元素
    for k in range(l, r+1):
        if i > mid:
            arrList[k] = aux[j-l]
            j = j + 1
        elif j > r:
            arrList[k] = aux[i-l]
            i = i + 1
        elif aux[i-l] <= aux[j-l]:
            arrList[k] = aux[i-l]
            i = i + 1
        else:
            arrList[k] = aux[j-l]
            j = j + 1

def __mergeSort(arrList, l, r):
    # 递归使用归并排序, 对arr[l...r]的范围进行排序
    # 处理递归到底的情况
    # 当l < r时，至少有两个元素需要处理
    if l >= r:
        return

    '''
    当粒度小到一定程度时，使用插入排序

    if r-l < 15:
        insertinSort(arrList, l, r)

        return
    '''

    # 最小粒度拆分
    # 对分开的左右两部分进行归并排序
    mid = int((l+r)/2)
    __mergeSort(arrList, l, mid)
    __mergeSort(arrList, mid+1, r)

    # 进行归并排序之后，已经保证每个部分都是有序的
    # 仅当arrList[mid] > arrList[mid+1]的时候，才需要进行merge操作
    # 对l->mid和mid+1->r进行merge操作
    if arrList[mid] > arrList[mid+1]:
        __merge(arrList, l, mid, r)

def mergeSort(arrList):
    __mergeSort(arrList, 0, len(arrList)-1)

a = [4, 3, 8, 1, 2, 3, 4, 1, 5, 7]
mergeSort(a)

print(a)
# [1, 1, 2, 3, 3, 4, 4, 5, 7, 8]

自底向上的归并排序算法

算法思想：
Python使用函数实现：