merge_sort.py

'''
Kyle C. Rosales (DarkPotatoKing)
October 8, 2014
Merge Sort
'''

def merge_sort(ls):

    def insertion_sort(ls):
        if len(ls) <= 1: return ls
        for i in xrange(1, len(ls)):
            j = i
            while j > 0 and ls[j-1] > ls[j]:
                ls[j-1], ls[j] = ls[j], ls[j-1]
                j -= 1
        return ls

    def merge_lists(list1, list2):
        temp = []
        while len(list1) > 0 or len(list2) > 0:
            if len(list1) == 0:
                while len(list2) > 0:
                    temp.append(list2.pop(0))
            elif len(list2) == 0:
                while len(list1) > 0:
                    temp.append(list1.pop(0))
            elif list1[0] < list2[0]: temp.append(list1.pop(0))
            else: temp.append(list2.pop(0))
        return temp

    #OPTIMIZATION: Switch to insertion sort for small data sets.
    if len(ls) <= 4:
        return insertion_sort(ls)

    mid = len(ls) / 2
    left_partition = ls[0:mid]
    right_partition = ls[mid:len(ls)]

    left_partition =  merge_sort(left_partition)
    right_partition =  merge_sort(right_partition)

    return merge_lists(left_partition, right_partition)