归并

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result


def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    num = len(lists)//2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

快排

def quick_sort(lists):
    less = []
    piv = []
    more = []
    if len(lists) <= 1:
        return lists
    p = lists[0]
    for i in lists:
        if i < p:
            less.append(i)
        elif i > p:
            more.append(i)
        else:
            piv.append(i)
    less = quick_sort(less)
    more = quick_sort(more)
    return less + piv + more