简单介绍

归并排序（英语：Merge sort，或mergesort），是建立在归并操作上的一种有效的排序算法，效率為 {\displaystyle O(n\log n)} {\displaystyle O(n\log n)}（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。维基百科

动图解释

代码实现

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Desc:

        归并排序，便于理解print了很多步骤，
    看着麻烦可以删除。

"""

i = 0


def merge_sort(_list):

    global i

    list_length = len(_list)

    if list_length == 1:

        return _list

    mid = list_length // 2

    print("{} 正在排序的列表: {}\n".format(i, _list))

    i += 1

    # 这里不断递归
    left_sorted_list = merge_sort(_list[:mid])

    print("左侧：{}".format(left_sorted_list))

    # 左侧列表完成后继续递归处理右侧列表
    right_sorted_list = merge_sort(_list[mid:])

    print("右侧：{}".format(right_sorted_list))

    result = merge(left_sorted_list, right_sorted_list)

    print(">>> 已经完成排序：{}\n".format(result))

    return result


def merge(left_list, right_list):

    left, right = 0, 0

    merge_result = list()

    left_length = len(left_list)

    right_length = len(right_list)

    while left < left_length and right < right_length:

        if left_list[left] <= right_list[right]:

            merge_result.append(left_list[left])

            left += 1

        else:

            merge_result.append(right_list[right])

            right += 1

    merge_result += left_list[left:]

    merge_result += right_list[right:]

    return merge_result


if __name__ == '__main__':
    _list = [54, 26, 93, 17, 77, 31, 44, 55, 20]

    print("等待排序的列表: %s\n-----" % _list)

    sorted_alist = merge_sort(_list)

    print("-----\n排序完成的列表：%s" % sorted_alist)