merge_sort.py

import random


def merge_sort(ints):
    length = len(ints)
    if length < 2:
        return ints
    mid = length >> 1
    left, right = merge_sort(ints[:mid]), merge_sort(ints[mid:])
    left_count, right_count = len(left), len(right)
    res = []
    i, j = 0, 0
    while i < left_count and j < right_count:
        if left[i] < right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    if i == left_count:
        res += right[j:]
    else:
        res += left[i:]
    return res


def test():
    ints = random.sample(range(1, 100), 10)
    print(ints)
    ints = merge_sort(ints)
    print(ints)
    for i in range(len(ints) - 1):
        if ints[i] > ints[i + 1]:
            print('Error')
            break


def main():
    for _ in range(1000):
        test()


if __name__ == '__main__':
    main()
# refer [归并排序](https://zh.wikipedia.org/wiki/归并排序)

归并排序，分简单，合并麻烦。