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