Merge Sort

merge_sort.py

"""
Merge Sort
"""


def merge(l1, l2):
    if len(l1) == 0 and len(l2) == 0:
        return []
    if len(l1) == 0 and len(l2) != 0:
        return l2[:]
    if len(l1) != 0 and len(l2) == 0:
        return l1[:]
    if l1[0] < l2[0]:
        return [l1[0]] + merge(l1[1:], l2)
    else:
        return [l2[0]] + merge(l1, l2[1:])


def merge_sort(l):
    length = len(l)
    if length <= 1:
        return l
    left_list = l[:length / 2]
    right_list = l[length / 2:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)

    return merge(left_list, right_list)

if __name__ == "__main__":
    test_list = [7, 5, 6, 3, 2, 1, 9, 8, 10]
    print merge_sort(test_list)