mergesort in python
729 ワード
def mergesort(List):
""" input : List, an integer list
output : an sorted integer list
"""
n = len(List)
if n == 0 or n==1:
return List
first = mergesort(List[:n/2])
second = mergesort(List[n/2:])
i=0
j=0
output = []
while True:
if first[i]<second[j]:
output.append(first[i])
i += 1
else:
output.append(second[j])
j += 1
if i >= len(first):
output += second[j:]
break
if j >= len(second):
output += first[i:]
break
return output