分而治之——归并-白红宇

分而治之——归并

阅读量：436 次

发布时间：2019-03-06

本文共 669 字，大约阅读时间需要 2 分钟。

# 分而治之
def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    else:
        mid = int(len(lists) / 2)
        left_half = merge_sort(lists[:mid])
        right_half = merge_sort(lists[mid:])
        new_lists = merge_sorted_list(left_half,right_half)
        return new_lists
def merge_sorted_list(sorted_a,sorted_b):
    length_a,length_b = len(sorted_a),len(sorted_b)
    a = b = 0
    new_sorted_list = list()
    while a < length_a and b < length_b:
        if sorted_a[a] < sorted_b[b]:
            new_sorted_list.append(sorted_a[a])
            a += 1
        else:
            new_sorted_list.append(sorted_b[b])
            b += 1
        
    while a < length_a:
        new_sorted_list.append(sorted_a[a])
        a += 1
    while b < length_b:
        new_sorted_list.append(sorted_b[b])
        b += 1
    
    return new_sorted_list