优化合并排序

Question

我需要优化我的排序（合并排序），这样对于大小为10^6的列表，将在不到100秒内进行排序。目前我最好的时间是105秒，我想不出一种方法来让这段代码更优化

def my_sort(lst):
if len(lst) > 1:
    puolivali = len(lst) // 2
    vas = lst[:puolivali]
    oik = lst[puolivali:]
    vas = my_sort(vas)
    oik = my_sort(oik)
    lst = []
    while len(vas) > 0 and len(oik) > 0:
        if vas[0] < oik[0]:
            lst.append(vas[0])
            vas.pop(0)
        else:
            lst.append(oik[0])
            oik.pop(0)

    for i in vas:
        lst.append(i)
    for i in oik:
        lst.append(i)

return lst

Answer 1

.pop(0)是主要的性能杀手，因为它转移了所有后续元素。请改用移动索引：

    # ...
    vas_i = oik_i = 0
    lst = []
    while vas_i < len(vas) and oik_i < len(oik):
        if vas[vas_i] < oik[oik_i]:
            lst.append(vas[vas_i])
            vas_i += 1
        else:
            lst.append(oik[oik_i])
            oik_i += 1

    lst.extend(vas[vas_i:])
    lst.extend(oik[oik_i:])

或作为一个完整的功能：

def my_sort(lst):
    mid = len(lst) // 2
    if mid:
        lo, hi = my_sort(lst[:mid]), my_sort(lst[mid:])
        lo_i = hi_i = 0
        lst = []
        while lo_i < len(lo) and hi_i < len(hi):
            if lo[lo_i] > hi[hi_i]:
                lo, lo_i, hi, hi_i = hi, hi_i, lo, lo_i
            lst.append(lo[lo_i])
            lo_i += 1
        lst.extend(lo[lo_i:])
        lst.extend(hi[hi_i:])
    return lst