```
def mergesort(lst, first=0, last=None):
if last == None:
last = len(lst)
#split the list in half
if last - first <= 1:
return
mid = first + (last - first) / 2
#run mergesort on each half
mergesort(lst, first, mid)
mergesort(lst, mid, last)
#create a temp array with mid - first number of elements
temp = range(mid - first)
#and copy left half into temp
for x in range(mid - first):
temp[x] = lst[first + x]
sp = first
right = mid
left = 0
#compare smallest elements from left half and right half
#put the smallest element in the next spot in the list
while left < len(temp) and right < last:
if lst[right] < temp[left]:
lst[sp] = lst[right]
right += 1
else:
lst[sp] = temp[left]
left += 1
sp += 1
#copy any remaining elements from temp into the end of the array
while left < len(temp):
lst[sp] = temp[left]
left += 1
sp += 1
```

Advertisements