Merge Sort

With recursion, it is simple:

def merge(L1, L2):
    Function to merge two sorted lists into one sorted one.
    Returns a new list that contains both elements of L1 and L2 in sorted order
    mergedList = []
    while i < len(L1) and j < len(L2):
        if L1[i] < L2[j]:
            i += 1
            j += 1

    while i < len(L1):
        i += 1

    while j < len(L2):
        j += 1

    return mergedList
def mergeSort(L):
    Function to sort the elements of the list using merge sort.
    Does not sort the list in place, but instead returns a new list which
    is sorted.
    if len(L) < 2:
        # an empty list or a list of one element is already sorted!
        return L
    mid = len(L)/2
    L1 = mergeSort(L[0:mid])
    L2 = mergeSort(L[mid:])
    mergedList = merge(L1, L2)
    return mergedList

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s