归并排序和快速排序

def merge_sort(arr):
    if len(arr) == 1:
        return arr
    p = 0
    n = len(arr)
    q = (p+n)//2
    return merge(arr, merge_sort(arr[p:q]), merge_sort(arr[q:]))


def merge(arr, arr1, arr2):
    temp = list()
    i = j = 0
    for r in range(len(arr)):
        if i < len(arr1) and j < len(arr2):
            # <= 保证稳定性
            if arr1[i] <= arr2[j]:
                temp.append(arr1[i])
                i += 1
            else:
                temp.append(arr2[j])
                j += 1
        else:
            if i < len(arr1):
                temp.extend(arr1[i:])
            else:
                temp.extend(arr2[j:])
            return temp

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    privot = arr[0]
    larr, rarr = partition(arr[1:], privot)
    return quick_sort(larr) + [privot] + quick_sort(rarr)


def partition(arr, privot):
    i = 0
    for j in range(len(arr)):
        if arr[j] < privot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
        j += 1
    return arr[:i], arr[i:]

归并排序可以保证稳定的O(nlogn)，但需要临时空间进行合并，空间复杂度O(n)。

快速排序平均复杂度是O(nlogn)，极端情况下O(n^2)，是不稳定的排序算法，不稳定的原因和选择排序相同（总是和“未排序”的第一个值交换），空间复杂度O(1)，极端情况出现的概率可以控制的很低加上空间占用低，所以快速排序应用广泛。

两种排序算法都使用了“分治”法，将大问题拆成多个小问题，由于各个部分采用相同的逻辑进行排序，所以通常使用"递归"的方式进行处理。

快排不稳定举例：5 3 2 5 1 假设privot=2，按照partition([5,3,5,1], 2)的结果是([1], [3, 5, 5])，显然最后一个5是一开始最前面的那个5