Pasted

# Functions to perform merge sort
# Uses Python2
 
def merge(list1, list2):
    """
   Merge two sorted lists.
 
   Returns a new sorted list containing those elements that are in
   either list1 or list2.
 
   This function can be iterative.
   """  
    merged = []
    first = list(list1)
    second = list(list2)
    while len(merged) < len(list1) + len(list2) and first and second:
        if first[0] < second[0]:
            merged.append(first.pop(0))
        else:
            merged.append(second.pop(0))
    merged += first
    merged += second
    return merged
               
def merge_sort(list1):
    """
   Sort the elements of list1.
 
   Return a new sorted list with the same elements as list1.
 
   This function should be recursive.
   """
    if len(list1) <= 1:
        return list1
    half = len(list1)/2
    return merge(merge_sort(list1[0:half]), merge_sort(list1[half:]))