mergesort.py

def mergesort(array, start=None, end=None):
  if start is None and end is None:
    return mergesort(array,0,len(array)-1)
  else:
    if start == end: return
    middle = start+(end-start)/2
    mergesort(array,start,middle)
    mergesort(array,middle+1,end)
    merge(array,start,middle,middle+1,end)
    return array

def merge(array, start1, end1, start2, end2):
  merged = []
  left = start1
  right = start2
  while len(merged)-1 < end2-start1:
    if left > end1 or right > end2:
      if left > end1:
        merged.append(array[right])
        right += 1
      else:
        merged.append(array[left])
        left += 1
    else:
      if array[left] < array[right]:
        merged.append(array[left])
        left += 1
      else:
        merged.append(array[right])
        right += 1
  for i in range(start1,end2+1):
    array[i] = merged[i-start1]