面试必备算法｜图解归并排序（Python）

归并排序

归并排序的思想

​ 归并排序主要使用了分治的策略进行排序，归并排序分为拆分和合并两个部分。拆分的时候我们需要递归的去执行把列表一分为二的操作（直到拆分成每个列表中只有一个元素），合并的时候我们同样使用递归的方法，不断地去比较列表中元素的大小并根据大小顺序进行合并（直到合并成一个列表）。

图解归并排序

​ 首先我们对整个列表进行不断的拆分（每次从中间拆开）：

​ 下一步就是对完全拆开的列表进行合并，合并的时候要比较元素之间的大小进行位置交换（每次递归都是如此）：

​ 完整的合并过程如下：

归并排序的性质

• 最优时间复杂度：$O(nlog_2n)$
• 最坏时间复杂度：$O(nlog_2n)$
• 稳定性：稳定

归并排序的代码实现

# 归并排序
lst = list(map(int, input().split(',')))


def mergeSort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        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


mergeSort(lst)