Merge Sort

gistfile1.py

from random import randint

def mergesort(unsorted):
    return unsorted if len(unsorted) < 2 else\
        merge(
            mergesort(unsorted[:(len(unsorted) + 1) / 2]),
            mergesort(unsorted[(len(unsorted) + 1) / 2:])
        )

def merge(left, right):
    merged, i, j = [], 0, 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    return merged + left[i:] + right[j:]


if __name__ == '__main__':
    unsorted = [randint(0, 1000) for i in range(10)]
    print 'Random: %s\nSorted: %s' % (unsorted, mergesort(unsorted))