【算法】归并排序 Merge Sort

算法介绍

归并排序，也叫合并排序，中心思想是将已排好序的两个或两个以上（常为两个）数列，合并成一个大的排序数列。为了保证这两个数列是已经排好序的，需要将数列对半分，直到该数列中只包含一个数字。

视频演示

视频地址：https://www.bilibili.com/video/av18980253

python 代码

#-*- coding: utf-8 -*-

# 升序
# 合并已经排好序的两个数列
def merge(left_data, right_data):
    merge_data = []
    L = len(left_data)
    R = len(right_data)
    i = 0
    j = 0
    while i<L and j<R:
        if left_data[i] < right_data[j]:
            merge_data.append(left_data[i])
            i += 1
        else:
            merge_data.append(right_data[j])
            j += 1
    # 结束后，i, j至少有一个到达最大值

    if i<L:
        assert j>=R
        merge_data.extend(left_data[i:])
    else:
        merge_data.extend(right_data[j:])
    return merge_data


# 递归将数据切分成两半，直到每边最多只有一个数
def merge_sort(data):
    n = len(data)
    if n<=1:
        return data
    else:
        middle = int(n//2) # 中间位置
        left_data = merge_sort(data[:middle]) # 左边数据
        right_data = merge_sort(data[middle:]) # 右边数据
        merge_data = merge(left_data, right_data) # 合并 左边数据 和 右边数据
        return merge_data


if __name__ == '__main__':
    data = [38, 27, 43, 3, 9, 82, 10]
    sorted_data = merge_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)

算法分析

归并排序需要递归切分 logn 次，时间复杂度为 O(nlogn)

归并排序空间复杂度跟实现方法有关系，最小为O(1)，最大为O(nlogn)