Skip to content

Instantly share code, notes, and snippets.

@fmasanori
Last active August 29, 2015 14:05
Show Gist options
  • Save fmasanori/d6aa74e1ca38888fbbfe to your computer and use it in GitHub Desktop.
Save fmasanori/d6aa74e1ca38888fbbfe to your computer and use it in GitHub Desktop.
mergesort
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))
@renzon
Copy link

renzon commented Aug 28, 2014

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment