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
    """
    i=0
    j=0
    mergedList = []
    
    while i < len(L1) and j < len(L2):
        if L1[i] < L2[j]:
            mergedList.append(L1[i])
            i += 1
        else:
            mergedList.append(L2[j])
            j += 1

    while i < len(L1):
        mergedList.append(L1[i])
        i += 1

    while j < len(L2):
        mergedList.append(L2[j])
        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
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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