归并排序

发表于 | 分类于

归并排序（Merge Sort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

算法描述

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

以列表 [54, 26, 93, 17, 77, 31, 44, 55, 20] 为例，归并排序算法的运作如下：

分层操作，9 个元素总共可以分成四层（直到最低层只有单个元素为止）：

归并操作，从低层到高层对已排序列表进行两两归并（单个元素可以看作是已排序列表）：

迭代法

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

递归法

原理如下（假设序列共有 n 个元素）：

  1. 将序列每相邻两个数字进行归并操作，形成 n/2 个序列
  2. 若此时序列数不是 1 则将上述序列再次归并，形成 n/4 个序列
  3. 重复步骤2，直到所有元素排序完毕，即序列数为 1

Python 实现

算法的 Python 代码如下（递归法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def merge(var1, var2):
    merge_list = []
    while var1 and var2:
        if var1[-1] < var2[-1]:
            merge_list = [var2.pop()] + merge_list
        else:
            merge_list = [var1.pop()] + merge_list
    if not var1:
        merge_list = var2 + merge_list
    else:
        merge_list = var1 + merge_list
    return merge_list


def merge_sort(var):
    if len(var) == 1:
        return var
    var_left = merge_sort(var[:len(var) // 2])
    var_right = merge_sort(var[len(var) // 2:])
    return merge(var_left,var_right)


s = [54, 26, 93, 17, 77, 31, 44, 55, 20]
s = merge_sort(s)  # not in-place sort, must use assignment '='
print(s)  # output: [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

  • 平均时间复杂度：$O(n\log n)$
  • 最坏时间复杂度：$O(n\log n)$