def mergeSort( aList ):
"""
Mergesort recursively divide the list into half, sort both halves
and then merge the two sorted lists into one.
"""
# If the aList is size 0 or 1, it's already sorted.
if len( aList ) <= 1:
return aList
else:
mid = len( aList ) // 2
# Recursively sort the left and right halves
left = mergeSort( aList[ :mid ] )
right = mergeSort( aList[mid:] )
# Merge the two (each sorted) parts back together
# return merge( left, right )
return mergelist( left, right ) # slightly different version of merge
def merge( left, right ):
"""
Merge to sorted list, left and right, into one sorted list.
"""
aList = []
lt = 0
rt = 0
# Repeatedly move the smallest of left and right to the new list
while lt < len( left ) and rt < len( right ):
if left[ lt ] < right[ rt ]:
aList.append( left[ lt ] )
lt += 1
else:
aList.append( right[ rt ] )
rt += 1
# There will only be elements left in one of the original two lists.
# Append the remains of left (lt..end) on to the new list.
while lt < len(left):
aList.append( left[ lt ] )
lt += 1
# Append the remains of right (rt..end) on to the new list.
while rt < len( right ):
aList.append( right[ rt ] )
rt += 1
return aList
def mergelist( left, right ):
"""
Mergeto sorted list, left and right, into one sorted list.
"""
aList = [None for x in range(len(left) + len(right))]
lt = 0
rt = 0
i = 0
# Repeatedly move the smallest of left and right to the new list
while lt < len( left ) and rt < len( right ):
if left[ lt ] < right[ rt ]:
aList[ i ] = left[ lt ]
lt += 1
else:
aList[ i ] = right[ rt ]
rt += 1
i += 1
# There will only be elements left in one of the original two lists.
# Append the remains of left (lt..end) on to the new list.
while lt < len(left):
aList[ i ] = left[ lt ]
lt += 1
i += 1
# Append the remains of right (rt..end) on to the new list.
while rt < len( right ):
aList[ i ]= right[ rt ]
rt += 1
i += 1
return aList