mergesort.py

from itertools import islice
import random


def merge_sort(l):
    if len(l) <= 1:
        return l
    left = []
    right = []
    middle = len(l) / 2
    for x in islice(l, middle):
        left.append(x)
    for x in islice(l, middle, None):
        right.append(x)
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)


def merge(left, right):
    result = []
    while left or right:
        if left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif left:
            result.append(left.pop(0))
        elif right:
            result.append(right.pop(0))
    return result


things = range(2000)
original = list(things)
random.shuffle(things)
final = merge_sort(things)
assert final == original, "This isnt right"