def mergesort(aList):
    """Return a sorted list with the given elements in ascending order.  Does not change the input list."""
    if len(aList) <= 1:
        # Base case.

        # Empty and singleton lists are already sorted.
        return aList
    else:
        # Recursive/inductive case:

        # Split list into two halves.  (Lengths will differ by at most one.)
        middle = len(aList)/2
        half1 = aList[:middle]
        half2 = aList[middle:]

        # Sort the two halves.
        half1Sorted = mergesort(half1)
        half2Sorted = mergesort(half2)

        # Merge the two sorted halves into a sorted whole.
        return merge(half1Sorted,half2Sorted)


# A recursive version of merging two sorted lists.
def merge(sorted1,sorted2):
    """Returns a sorted list with the elements in the given sorted lists."""
    if sorted1 == []:
        # Base case 1:  first sorted list has no elements
        
        # Merging is unnecessary.  Return the already-sorted elements in the other list.
        return sorted2

    elif sorted2 == []:
        # Base case 2:  second sorted list has no elements

        # Merging is unnecessary.  Return the already-sorted elements in the other list.
        return sorted1

    else:
        # Recursive/inductive case:  both lists have elements

        # Compare the first elements of each input.
        first1 = sorted1[0]
        first2 = sorted2[0]
        if first1 < first2:
            # first1 is the smallest element and should be the first element of the result.
            # Merge the rest of the input.
            restSorted = merge(sorted1[1:],sorted2)
            restSorted.insert(0,first1)
        else:
            # first2 is the smallest element and should be the first element of the result.
            # Merge the rest of the input.
            restSorted = merge(sorted1,sorted2[1:])
            restSorted.insert(0,first2)
        return restSorted


# A looping version of merging two sorted lists.
def merge2(sorted1,sorted2):
    """Returns a sorted list with the elements in the given sorted lists."""

    # We keep a "finger" pointing to the next element to consider in each list.

    result = []
    position1 = 0
    position2 = 0
    
    while position1 < len(sorted1) and position2 < len(sorted2):
        # There are still elements to consider in each list.

        # Compare the next element in each list.
        if sorted1[position1] < sorted2[position2]:
            # The next element of the first list is smaller.
            # Add it to the result, and move the appropriate "finger".
            result.append(sorted1[position1])
            position1 += 1
        else:
            # The next element of the second list is smaller.
            # Add it to the result, and move the appropriate "finger".
            result.append(sorted2[position2])
            position2 += 1

    # One list's elements have all been added to the result.
    # Add the remaining elements of the other list to the result.
    if position1 == len(sorted1):
        result.extend(sorted2[position2:])
    else
        result.extend(sorted1[position1:])

    return result