import sys

def merge(nums,first,middle,last):
  lnums = nums[first:middle+1]
  rnums = nums[middle+1:last+1]
  lnums.append(sys.maxint)
  rnums.append(sys.maxint)
  l=0
  r = 0
for i in range(first,last+1):
  if lnums[l] <rnums[r]:
    nums[i] = lnums[l]
    l+=1
else:
  nums[i] = rnums[r]
  r+=1

def merge_sort(nums,first,last):
  if first<last:
    middle = (first + last)/2
    merge_sort(nums,first,middle)
    merge_sort(nums,middle+1,last)
    merge(nums,first,middle,last)

if __name__==‘__main__‘:
nums = [10,3,34,67,-34,4,2]
print ‘nums is:‘,nums
merge_sort(nums,0,7)
print ‘merge sort:‘,nums

Python实现归并排序