mergesort

mergesort.py

def merge(e, d):
    r = []
    i, j = 0, 0
    while i < len(e) and j < len(d):
        if e[i] <= d[j]:
            r.append(e[i])
            i += 1
        else:
            r.append(d[j])
            j += 1
    r += e[i:]
    r += d[j:]
    return r

def mergesort(v):
    if len(v) <= 1:
        return v
    else:
        m = len(v) // 2
        e = mergesort(v[:m])
        d = mergesort(v[m:])
        return merge(e, d)

from random import shuffle
v = list(range(16))
shuffle(v)
print (v)
print (mergesort(v))

del e[0] é O(n)? Se for, essa implementação de mergesort tá O(n^2 logn).

Minha tentativa.

def merge(e, d):
    i, j = 0, 0    
    while i < len(e) or j < len(d):
        if j>=len(d) or i<len(e) and e[i] <= d[j]:
            yield e[i] 
            i+=1
        else:
            yield d[j]
            j+=1

def mergesort(v):
    if len(v) <= 1:
        return v

    m = len(v) // 2
    e = mergesort(v[:m])
    d = mergesort(v[m:]) 
    return list(merge(e, d))

print mergesort([1,3,2,5,-10])

Já que está utilizando slice, que tal trocar o del por ele:

def merge(e, d):
    r = []
    while len(e) > 0 and len(d) > 0:
        if e[0] <= d[0]:
            r.append(e[0])
            e = e[1:]
        else:
            r.append(d[0])
            d = d[1:]
    r += e
    r += d
    return r


def mergesort(v):
    if len(v) <= 1:
        return v
    else:
        m = len(v) // 2
        e = mergesort(v[:m])
        d = mergesort(v[m:])
        return merge(e, d)