# Jay Summet
# CS 1301 - Released to the public domain, November 2007

#Merge Sort

aList = [ -1, 4.5 ]
bList = [5, 7.3]

#Merge:
# When given two (already sorted) lists (of numbers), returns a merged version 
def merge2(listA,listB):
    counterA = 0
    counterB = 0

    resultList = []

    if len(listA) == 0 and len(listB) == 0:
        return( resultList)
    if len(listA) == 0:
        return(listB)
    if len(listB) == 0:
        return(listA)

    while( counterA < len(listA) and counterB < len(listB) ):
        if (listA[counterA] < listB[counterB]):
            resultList.append( listA[counterA])
            counterA = counterA + 1
        else:
            resultList.append( listB[counterB])
            counterB = counterB + 1

    if counterB < len(listB):
        resultList = resultList + listB[counterB:]
    else:
        resultList = resultList + listA[counterA:]


    return(resultList)

#Test code for the merge2 function        
#print "listA: ", aList, "listB:", bList
#resultList = merge2(aList,bList)
#print resultList



cList = [ 45, -3, 10, 18, 5]


#Given a list of (potentially unsorted) numbers, this function
# will sort them using the mergesort algorithm.
def mergeSort(aList):
    if len(aList) < 2:
        return(aList)


    middle = len(aList) / 2

    firstHalf = aList[:middle]
    secondHalf = aList[middle:]

    firstHalfSorted = mergeSort(firstHalf)
    secondHalfSorted = mergeSort(secondHalf)

    result = merge2(firstHalfSorted, secondHalfSorted)

    return(result)


#Test code for the mergeSort function
print "cList: " ,cList
ourResult = mergeSort(cList)
print ourResult