mergesort.py

import random


def merge(lista, listb):
    pa = 0
    pb = 0
    result = []
    while True:
        if lista[pa] <= listb[pb]:
            result.append(lista[pa])
            pa += 1
            if pa >= len(lista):
                result += listb[pb:]
                break
        else:
            result.append(listb[pb])
            pb += 1
            if pb >= len(listb):
                result += lista[pa:]
                break

    return result


def mergesort(_list):
    '''Takes _list and returns a sorted version of it, using mergesort'''
    if len(_list) <= 1:
        return _list

    middle = int(len(_list) / 2)
    left = _list[:middle]
    right = _list[middle:]
    return merge(mergesort(left), mergesort(right))


if __name__ == '__main__':
    print "MERGESORT the following list"
    random_ints = [random.randint(0, 1000) for r in xrange(1000)]
    print random_ints
    print "Now sorted:\n"
    print mergesort(random_ints)