归并排序的python实现

代码:

# -*- coding: utf-8 -*-
"""归并排序"""
import random

def merge(left, right):
    """合并两个数组"""
    merged = []
    # i, j 分别作为left和right的下标
    i, j = 0, 0
    left_len, right_len = len(left), len(right)
    while i < left_len and j < right_len:
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    middle = len(lst) // 2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)


if __name__ == '__main__':
    lst = []
    for i in range(30):
        lst.append(random.randint(1, 100))
    print lst
    result = merge_sort(lst)
    print result