Mergesort em python

Question

Minha implementação de mergesort atualmente leva muito tempo, para uma lista com 1 milhão de elementos leva mais de 130 segundos para ter a lista classificada.

• Alguém poderia gentilmente dar uma olhada no meu código e sugerir o que eu poderia fazer para melhorá-lo?

• Existe algo em particular no meu código que está demorando muito?

Código

def splitlist(L): #splits the list to a list of individual listed elements (e.g. [1,2] to [[1],[2]])
    envelop = lambda x: [x]
    return(list(map(envelop,L)))


def merge(L_1,L_2): #merges two (already sorted) lists to one sorted list
    N = []
    while len(L_1) > 0 and len(L_2) > 0:
        if L_1[0] > L_2[0]:
            N += [L_2.pop(0)]
        else:
            N += [L_1.pop(0)]
    if len(L_1) == 0:
        N += L_2
    else:
        N += L_1
        
    return(N)


#performs one round of pairwise merges (e.g. [[2],[1],[4],[3]] to [[1,2],[3,4]]), or [[5,10],[1,8],[2,3]] to [[1,2,3,5,8,10]])   
def mergelist(L): 
    N = []
    if len(L) % 2 == 0:
        for i in range(0,len(L)//2):
            N += [merge(L[2*i],L[2*i + 1])]
    else:
        for i in range(0,len(L)//2 - 1):
            N += [merge(L[2*i],L[2*i + 1])]
        N += [merge(merge(L[-3],L[-2]),L[-1])]
    
    return(N)

def mergesort(L): #recursively performs mergelist until there is only 1 sorted list remaining
    L = splitlist(L)
    while len(L) > 1:
        L = mergelist(L)
    return(L[0])

Aqui está meu código para gerar os milhões de elementos:

rlist = random.sample(range(0,2000000),1000000)

Answer 1

A pop(0)leva tempo linear. Faça isso de forma diferente, no tempo O (1). A forma padrão usa variáveis ​​de índice. Veja as respostas desta pergunta para algumas formas mais pythônicas. Ou você pode mesclar da direita para a esquerda, usando pop(), e no final reverse()o resultado.

Uma maneira de fazer o último:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    N = []
    while L1 and L2:
        L = L1 if L1[-1] > L2[-1] else L2
        N.append(L.pop())
    N.reverse()
    N[:0] = L1 or L2
    return N

Outras alterações que fiz e que você também pode aplicar em outras partes do seu código:

• Removido os sublinhados das variáveis, acho que lê melhor. Eu os mantive em letras maiúsculas porque L, para , é o que diz o PEP 8 . E então eu mantive Na consistência. Normalmente eu usaria resultou talvez merged. Não sei por que você escolheu N. Se você tiver uma palavra significativa que começa com "n", sugiro usá-la.
• Espaço entre os parâmetros da função.
• Formato de docstring adequado em vez de comentário.
• Substituído len(L_1) > 0pela verificação normal de L1ausência de vazio.
• Substituído N += [x]pelo normal N.append(x).

Apenas outra maneira, substituindo aquela linha "longa" para determinar Lpor uma forma mais clara, porém mais lenta:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    N = []
    def last(L):
        return L[-1]
    while L1 and L2:
        L = max(L2, L1, key=last)
        N.append(L.pop())
    N.reverse()
    N[:0] = L1 or L2
    return N

Para se divertir, dois hacks de compreensão de lista:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    def end(L):
        return L[-1:]
    return [max(L2, L1, key=end).pop() for _ in L1 + L2][::-1]

def merge(L, R):
    """Merges two (already sorted) lists to one sorted list."""
    return [(R, L)[L[-1:] > R[-1:]].pop() for _ in L + R][::-1]

E não quero sair sem um caminho muito mais rápido:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    return sorted(L1 + L2)

Isso é O (n) por causa de Timsort. E rápido O (n) por causa do código C. Se você acha que usar o poderoso sorteddentro de um mergesort anula o propósito de escrever o mergesort em primeiro lugar: Até mesmo isso pode ser significativo, se você não estiver apenas fazendo mergesort. Pelo menos uma vez eu escrevi um mergesort com contagem incorporada de algo, e de fato usei sortedapenas para a fusão. Porque isso tornou minha solução mais rápida / curta / simples.

Ainda mais eficiente (espaço e tempo):

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    L1 += L2
    L1.sort()
    return L1

(Se L2puder ser maior que L1, pode ser vantajoso inserir L1em L2vez disso.)