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))

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)