归并排序

# 归并排序
import sys
def merge_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    mid = n//2
    
    L = merge_sort(arr[:mid])
    R = merge_sort(arr[mid:])
        
    n_l = len(L)
    n_r = len(R)
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    
    i, j = 0, 0
    new_arr = []
    while i < n_l or j < n_r:
        if L[i] <= R[j]:
            new_arr.append(L[i])
            i += 1
        else:
            new_arr.append(R[j])
            j += 1
    return new_arr

快速排序

# 快速排序
def quick_sort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    
    mask = arr.pop()
    L, R = [], []
    for i in range(len(arr)):
        if arr[i] < mask:
            L.append(arr[i])
        else:
            R.append(arr[i])
    return quick_sort(L)+[mask]+quick_sort(R)